Submission #596482


Source Code Expand

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAXN = 2010;
const int MAXM = 1000000;
const long long INF = 100000000000000000LL;
struct Edge
{
    int to,next,cap,flow;
	long long cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN];
long long dis[MAXN];
bool vis[MAXN];
int N;//节点总个数,节点编号从0~N-1
void init(int n)
{
    N = n;
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,long long cost)
{
    edge[tol].to = v;
    edge[tol].cap = cap;
    edge[tol].cost = cost;
    edge[tol].flow = 0;
    edge[tol].next = head[u];
    head[u] = tol++;
    edge[tol].to = u;
    edge[tol].cap = 0;
    edge[tol].cost = -cost;
    edge[tol].flow = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
}
bool spfa(int s,int t)
{
    queue<int>q;
    for(int i = 0;i < N;i++)
    {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1;i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow &&
               dis[v] > dis[u] + edge[i].cost )
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1)return false;
    else return true;
}
//返回的是最大流,cost存的是最小费用
int minCostMaxflow(int s,int t,long long &cost)
{
    int flow = 0;
    cost = 0;
    while(spfa(s,t))
    {
        long long Min = INF;
        for(int i = pre[t];i != -1;i = pre[edge[i^1].to])
        {
            if(Min > edge[i].cap - edge[i].flow)
                Min = edge[i].cap - edge[i].flow;
        }
        for(int i = pre[t];i != -1;i = pre[edge[i^1].to])
        {
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

pair<int,int>p[1000];
pair<int,int>da[1000];
pair<int,int>de[1000];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
	while(scanf("%d",&n) == 1) {
		for(int i = 0;i < n;i++) {
			scanf("%d%d", &p[i].first, &p[i].second);
		}
		long long sum = 0;
		int num1 = 0;
		int num2 = 0;
		int cnt = 0;
		for (int i = n-1;i >= 0;i--) {
			if (p[i].first == 2) {
				sum += p[i].second;
				cnt++;
			} else if (p[i].first == 0) {
				da[num1++] = make_pair(cnt, p[i].second);
			} else {
				de[num2++] = make_pair(cnt, p[i].second);
			}
		}
		init(num1+num2+2);
		for (int i = 1;i <= num1;i++)addedge(0,i,1,0);
		for (int i = num1+1;i <= num1+num2;i++)addedge(i,num1+num2+1,1,0);
		for (int i = 0;i < num1;i++)
			for(int j = 0;j < num2;j++) {
				long long cost = (long long)min(da[i].first, de[j].first)*de[j].second - da[i].second;
				if (cost < 0)cost = 0;
				addedge(i+1, num1+1+j, 1, -cost);
			}
		long long tmp;
		minCostMaxflow(0, num1+num2+1, tmp);
		long long ans = sum + tmp;
		printf("%lld\n",ans);
	}
    return 0;
}

Submission Info

Submission Time
Task H - Dungeon
User kuangbin
Language C++ (G++ 4.6.4)
Score 100
Code Size 3570 Byte
Status AC
Exec Time 2422 ms
Memory 5220 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:120:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 58
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All colorful1_01.txt, colorful1_02.txt, colorful1_03.txt, colorful2_01.txt, colorful2_02.txt, colorful2_03.txt, colorful3_01.txt, colorful3_02.txt, colorful3_03.txt, corner_01.txt, corner_02.txt, corner_03.txt, corner_04.txt, corner_05.txt, corner_06.txt, interval_01.txt, interval_02.txt, interval_03.txt, interval_04.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_exp_01.txt, random_exp_02.txt, random_exp_03.txt, random_max_01.txt, random_max_02.txt, random_max_03.txt, random_max_04.txt, random_max_05.txt, random_max_06.txt, random_max_07.txt, random_max_08.txt, random_max_09.txt, random_max_10.txt, random_select_01.txt, random_select_02.txt, random_select_03.txt, random_select_04.txt, random_select_05.txt, random_select_06.txt, random_select_07.txt, random_select_08.txt, random_select_09.txt, random_select_10.txt, random_small_01.txt, random_small_02.txt, random_small_03.txt, random_small_04.txt, random_small_05.txt, random_small_06.txt, random_small_07.txt, random_small_08.txt, random_small_09.txt, random_small_10.txt
Case Name Status Exec Time Memory
colorful1_01.txt AC 220 ms 2032 KB
colorful1_02.txt AC 152 ms 1964 KB
colorful1_03.txt AC 216 ms 2004 KB
colorful2_01.txt AC 2199 ms 5164 KB
colorful2_02.txt AC 1289 ms 5160 KB
colorful2_03.txt AC 1412 ms 5160 KB
colorful3_01.txt AC 1267 ms 5168 KB
colorful3_02.txt AC 1145 ms 5164 KB
colorful3_03.txt AC 1057 ms 5164 KB
corner_01.txt AC 25 ms 880 KB
corner_02.txt AC 25 ms 1048 KB
corner_03.txt AC 24 ms 980 KB
corner_04.txt AC 53 ms 1368 KB
corner_05.txt AC 25 ms 1040 KB
corner_06.txt AC 25 ms 1044 KB
interval_01.txt AC 30 ms 1304 KB
interval_02.txt AC 1105 ms 5164 KB
interval_03.txt AC 1314 ms 5156 KB
interval_04.txt AC 307 ms 2976 KB
random_01.txt AC 1434 ms 5168 KB
random_02.txt AC 1414 ms 5156 KB
random_03.txt AC 1157 ms 5164 KB
random_04.txt AC 1058 ms 5156 KB
random_05.txt AC 1230 ms 5112 KB
random_06.txt AC 1044 ms 5156 KB
random_exp_01.txt AC 26 ms 1064 KB
random_exp_02.txt AC 25 ms 1044 KB
random_exp_03.txt AC 26 ms 1048 KB
random_max_01.txt AC 1964 ms 5164 KB
random_max_02.txt AC 1839 ms 5160 KB
random_max_03.txt AC 2375 ms 5220 KB
random_max_04.txt AC 1529 ms 5160 KB
random_max_05.txt AC 1925 ms 5160 KB
random_max_06.txt AC 1930 ms 5164 KB
random_max_07.txt AC 2422 ms 5160 KB
random_max_08.txt AC 2280 ms 5160 KB
random_max_09.txt AC 1809 ms 5164 KB
random_max_10.txt AC 1595 ms 5160 KB
random_select_01.txt AC 722 ms 3096 KB
random_select_02.txt AC 610 ms 2988 KB
random_select_03.txt AC 503 ms 3096 KB
random_select_04.txt AC 667 ms 3092 KB
random_select_05.txt AC 509 ms 3104 KB
random_select_06.txt AC 582 ms 3096 KB
random_select_07.txt AC 725 ms 3092 KB
random_select_08.txt AC 563 ms 3116 KB
random_select_09.txt AC 464 ms 3116 KB
random_select_10.txt AC 638 ms 2988 KB
random_small_01.txt AC 25 ms 1044 KB
random_small_02.txt AC 26 ms 1048 KB
random_small_03.txt AC 26 ms 1048 KB
random_small_04.txt AC 25 ms 1048 KB
random_small_05.txt AC 31 ms 1048 KB
random_small_06.txt AC 32 ms 1064 KB
random_small_07.txt AC 37 ms 1308 KB
random_small_08.txt AC 53 ms 1320 KB
random_small_09.txt AC 68 ms 1324 KB
random_small_10.txt AC 86 ms 1460 KB
sample_01.txt AC 26 ms 1040 KB
sample_02.txt AC 26 ms 856 KB
sample_03.txt AC 26 ms 856 KB