Submission #596475


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 = 1000010;
const long long INF = 1000000000000000000LL;
struct Edge
{
    int to,next,cap,flow;
	long long cost;
	Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,long long _cost = 0):
		to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost){}
}edge[MAXM];

struct ZKW_MinCostMaxFlow
{
	int head[MAXN],tot;
	int cur[MAXN];
	long long dis[MAXN];
	bool vis[MAXN];
	int ss,tt,N;//源点、汇点和点的总个数(编号是0~N-1),不需要额外赋值,调用会直接赋值
	long long min_cost;
   	int 	max_flow;
	void init()
	{
		tot = 0;
		memset(head,-1,sizeof(head));
	}
	void addedge(int u,int v,int cap,long long cost)
	{
		edge[tot] = Edge(v,head[u],cap,0,cost);
		head[u] = tot++;
		edge[tot] = Edge(u,head[v],0,0,-cost);
		head[v] = tot++;
	}
	int aug(int u,int flow)
	{
		if(u == tt)return flow;
		vis[u] = true;
		for(int i = cur[u];i != -1;i = edge[i].next)
		{
			int v = edge[i].to;
			if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] == dis[v] + edge[i].cost)
			{
				int tmp = aug(v,min(flow,edge[i].cap-edge[i].flow));
				edge[i].flow += tmp;
				edge[i^1].flow -= tmp;
				cur[u] = i;
				if(tmp)return tmp;
			}
		}
		return 0;
	}
	bool modify_label()
	{
		long long d = INF;
		for(int u = 0;u < N;u++)
			if(vis[u])
				for(int i = head[u];i != -1;i = edge[i].next)
				{
					int v = edge[i].to;
					if(edge[i].cap>edge[i].flow && !vis[v])
						d = min(d,dis[v]+edge[i].cost-dis[u]);
				}
		if(d == INF)return false;
		for(int i = 0;i < N;i++)
			if(vis[i])
			{
				vis[i] = false;
				dis[i] += d;

			}
		return true;
	}
	/*
	 * 直接调用获取最小费用和最大流
	 * 输入: start-源点,end-汇点,n-点的总个数(编号从0开始)
	 * 返回值: pair<int,int> 第一个是最小费用,第二个是最大流
	 */
	pair<long long,int> mincostmaxflow(int start,int end,int n)
	{
		ss = start, tt = end, N = n;
		min_cost = 0;
	   	max_flow = 0;
		for(int i = 0;i < n;i++)dis[i] = 0;
		while(1)
		{
			for(int i = 0;i < n;i++)cur[i] = head[i];
			while(1)
			{
				for(int i = 0;i < n;i++)vis[i] = false;
				int tmp = aug(ss,1000000000);
				if(tmp == 0)break;
				max_flow += tmp;
				min_cost += tmp*dis[ss];
			}
			if(!modify_label())break;
		}
		return make_pair(min_cost,max_flow);
	}
}solve;

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);
			}
		}
		solve.init();
		for (int i = 1;i <= num1;i++)solve.addedge(0,i,1,0);
		for (int i = num1+1;i <= num1+num2;i++)solve.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;
				solve.addedge(i+1, num1+1+j, 1, -cost);
			}
		pair<long long,int>tmp = solve.mincostmaxflow(0,num1+num2+1,num1+num2+2);
		long long ans = sum + tmp.first;
		printf("%lld\n",ans);
	}
    return 0;
}

Submission Info

Submission Time
Task H - Dungeon
User kuangbin
Language C++ (G++ 4.6.4)
Score 0
Code Size 3809 Byte
Status WA
Exec Time 1599 ms
Memory 24424 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:125: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 0 / 100
Status
AC × 3
AC × 8
WA × 50
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 WA 84 ms 24412 KB
colorful1_02.txt WA 70 ms 24360 KB
colorful1_03.txt WA 76 ms 24368 KB
colorful2_01.txt WA 165 ms 24360 KB
colorful2_02.txt WA 75 ms 24360 KB
colorful2_03.txt WA 77 ms 24360 KB
colorful3_01.txt WA 1599 ms 24416 KB
colorful3_02.txt WA 1184 ms 24364 KB
colorful3_03.txt WA 1389 ms 24424 KB
corner_01.txt AC 74 ms 24364 KB
corner_02.txt AC 73 ms 24364 KB
corner_03.txt AC 76 ms 24360 KB
corner_04.txt AC 73 ms 24360 KB
corner_05.txt AC 70 ms 24364 KB
corner_06.txt AC 70 ms 24364 KB
interval_01.txt WA 72 ms 24356 KB
interval_02.txt WA 78 ms 24364 KB
interval_03.txt WA 273 ms 24364 KB
interval_04.txt WA 80 ms 24364 KB
random_01.txt WA 78 ms 24368 KB
random_02.txt WA 82 ms 24368 KB
random_03.txt WA 76 ms 24368 KB
random_04.txt WA 119 ms 24256 KB
random_05.txt WA 85 ms 24296 KB
random_06.txt WA 115 ms 24300 KB
random_exp_01.txt WA 72 ms 24300 KB
random_exp_02.txt WA 72 ms 24296 KB
random_exp_03.txt AC 72 ms 24300 KB
random_max_01.txt WA 80 ms 24304 KB
random_max_02.txt WA 212 ms 24308 KB
random_max_03.txt WA 533 ms 24236 KB
random_max_04.txt WA 195 ms 24300 KB
random_max_05.txt WA 202 ms 24296 KB
random_max_06.txt WA 89 ms 24308 KB
random_max_07.txt WA 603 ms 24304 KB
random_max_08.txt WA 231 ms 24292 KB
random_max_09.txt WA 83 ms 24304 KB
random_max_10.txt WA 153 ms 24300 KB
random_select_01.txt WA 72 ms 24304 KB
random_select_02.txt WA 71 ms 24300 KB
random_select_03.txt WA 69 ms 24300 KB
random_select_04.txt WA 70 ms 24292 KB
random_select_05.txt WA 69 ms 24300 KB
random_select_06.txt WA 70 ms 24292 KB
random_select_07.txt WA 70 ms 24292 KB
random_select_08.txt WA 70 ms 24300 KB
random_select_09.txt WA 69 ms 24300 KB
random_select_10.txt WA 69 ms 24304 KB
random_small_01.txt AC 68 ms 24284 KB
random_small_02.txt WA 68 ms 24284 KB
random_small_03.txt WA 72 ms 24280 KB
random_small_04.txt WA 68 ms 24300 KB
random_small_05.txt WA 70 ms 24292 KB
random_small_06.txt WA 69 ms 24292 KB
random_small_07.txt WA 70 ms 24300 KB
random_small_08.txt WA 68 ms 24296 KB
random_small_09.txt WA 69 ms 24300 KB
random_small_10.txt WA 89 ms 24336 KB
sample_01.txt AC 68 ms 24296 KB
sample_02.txt AC 68 ms 24296 KB
sample_03.txt AC 68 ms 24300 KB