Submission #478139


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#define SIZE 905
#define MX 305
#define INF 1000000000

using namespace std;
typedef long long int ll;
typedef pair <int,ll> P;

struct MinCost
{
	struct edge
	{
		int to,cap,rev;
		ll cost;
		edge(int to=-1,int cap=-1,ll cost=-1,int rev=-1):to(to),cap(cap),cost(cost),rev(rev){}
	};
	vector <edge> vec[SIZE];
	bool use[SIZE];
	ll d[SIZE];
	int pv[SIZE],pe[SIZE];
	int n,m;

	void add(int start,int end,int cap,ll cost)
	{
		int s=vec[start].size(),e=vec[end].size();
		vec[start].push_back(edge(end,cap,cost,e));
		vec[end].push_back(edge(start,0,-cost,s));
	}
	ll min_cost(int s,int t)
	{
		ll flow=0;
		while(1)
		{
			fill(d,d+n,INF);
			memset(use,false,sizeof(use));
			d[s]=0;
			for(int T=0;T<=n;T++)
			{
				bool up=false;
				for(int i=0;i<n;i++)
				{
					for(int j=0;j<vec[i].size();j++)
					{
						edge e=vec[i][j];
						if(e.cap>0&&d[e.to]>d[i]+e.cost)
						{
							d[e.to]=d[i]+e.cost;
							pv[e.to]=i;
							pe[e.to]=j;
							up=true;
						}
					}
				}
				if(!up) break;
			}
			if(d[t]>=0) return flow;
			int dt=INF;
			for(int v=t;v!=s;v=pv[v]) dt=min(dt,vec[pv[v]][pe[v]].cap);
			flow+=(ll) dt*d[t];
			for(int v=t;v!=s;v=pv[v])
			{
				edge&e=vec[pv[v]][pe[v]];
				e.cap-=dt;
				vec[e.to][e.rev].cap+=dt;
			}
		}
	}
};
MinCost solve;
int A[SIZE];
ll B[SIZE];
P key[SIZE],def[SIZE];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d %lld",&A[i],&B[i]);
	ll sum=0;
	int sk=0,sd=0,now=0;
	for(int i=n-1;i>=0;i--)
	{
		if(A[i]==2)
		{
			sum+=B[i];
			now++;
		}
		else if(A[i]==0)
		{
			key[sk++]=P(now,B[i]);
		}
		else
		{
			def[sd++]=P(now,B[i]);
		}
	}
	int s=sk+sd,t=s+1;
	solve.n=t+2;
	for(int i=0;i<sk;i++) solve.add(s,i,1,0);
	for(int i=0;i<sd;i++) solve.add(i+sk,t,1,0);
	for(int i=0;i<sk;i++)
	{
		for(int j=0;j<sd;j++)
		{
			ll cost=(ll) min(key[i].first,def[j].first)*def[j].second-key[i].second;
			//printf("%d %d %lld\n",i,j,cost);
			if(cost>0)
			{
				solve.add(i,j+sk,1,-cost);
			}
		}
	}
	printf("%lld\n",sum+solve.min_cost(s,t));
	return 0;
}

Submission Info

Submission Time
Task H - Dungeon
User yutaka1999
Language C++ (G++ 4.6.4)
Score 0
Code Size 2265 Byte
Status TLE
Exec Time 5034 ms
Memory 6104 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:84:51: 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 × 57
TLE × 1
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 61 ms 1496 KB
colorful1_02.txt AC 30 ms 988 KB
colorful1_03.txt AC 67 ms 1444 KB
colorful2_01.txt AC 470 ms 3556 KB
colorful2_02.txt AC 41 ms 1304 KB
colorful2_03.txt AC 90 ms 1812 KB
colorful3_01.txt AC 228 ms 3148 KB
colorful3_02.txt AC 257 ms 3156 KB
colorful3_03.txt AC 620 ms 6104 KB
corner_01.txt AC 27 ms 912 KB
corner_02.txt AC 25 ms 924 KB
corner_03.txt AC 24 ms 852 KB
corner_04.txt AC 26 ms 916 KB
corner_05.txt AC 25 ms 924 KB
corner_06.txt AC 26 ms 928 KB
interval_01.txt AC 28 ms 1180 KB
interval_02.txt AC 39 ms 1564 KB
interval_03.txt AC 158 ms 3028 KB
interval_04.txt AC 58 ms 2072 KB
random_01.txt AC 110 ms 2388 KB
random_02.txt AC 201 ms 3028 KB
random_03.txt AC 60 ms 1880 KB
random_04.txt AC 207 ms 3288 KB
random_05.txt AC 170 ms 3024 KB
random_06.txt AC 160 ms 3152 KB
random_exp_01.txt AC 27 ms 1120 KB
random_exp_02.txt TLE 5034 ms 984 KB
random_exp_03.txt AC 26 ms 920 KB
random_max_01.txt AC 368 ms 3416 KB
random_max_02.txt AC 383 ms 3732 KB
random_max_03.txt AC 510 ms 3664 KB
random_max_04.txt AC 364 ms 3536 KB
random_max_05.txt AC 423 ms 3352 KB
random_max_06.txt AC 435 ms 3540 KB
random_max_07.txt AC 456 ms 3560 KB
random_max_08.txt AC 461 ms 3536 KB
random_max_09.txt AC 387 ms 3416 KB
random_max_10.txt AC 374 ms 3668 KB
random_select_01.txt AC 261 ms 2516 KB
random_select_02.txt AC 217 ms 2516 KB
random_select_03.txt AC 198 ms 2388 KB
random_select_04.txt AC 181 ms 2252 KB
random_select_05.txt AC 180 ms 2264 KB
random_select_06.txt AC 226 ms 2380 KB
random_select_07.txt AC 272 ms 2384 KB
random_select_08.txt AC 229 ms 2640 KB
random_select_09.txt AC 163 ms 2264 KB
random_select_10.txt AC 221 ms 2460 KB
random_small_01.txt AC 26 ms 920 KB
random_small_02.txt AC 24 ms 920 KB
random_small_03.txt AC 25 ms 924 KB
random_small_04.txt AC 26 ms 928 KB
random_small_05.txt AC 28 ms 1048 KB
random_small_06.txt AC 28 ms 980 KB
random_small_07.txt AC 31 ms 1108 KB
random_small_08.txt AC 35 ms 1108 KB
random_small_09.txt AC 37 ms 1312 KB
random_small_10.txt AC 42 ms 1308 KB
sample_01.txt AC 23 ms 920 KB
sample_02.txt AC 26 ms 848 KB
sample_03.txt AC 26 ms 860 KB