Submission #478141


Source Code Expand

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

using namespace std;
typedef long long int ll;
typedef pair <ll,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];
	ll h[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;
		memset(h,0,sizeof(h));
		while(1)
		{
			priority_queue <P,vector <P>,greater <P> > que;
			for(int i=0;i<n;i++) d[i]=LINF;
			d[s]=0;
			que.push(P(0,s));
			while(!que.empty())
			{
				P p=que.top();que.pop();
				int v=p.second;
				if(d[v]<p.first) continue;
				for(int i=0;i<vec[v].size();i++)
				{
					edge&e=vec[v][i];
					if(e.cap>0&&d[e.to]>d[v]+e.cost+h[v]-h[e.to])
					{
						d[e.to]=d[v]+e.cost+h[v]-h[e.to];
						pv[e.to]=v;
						pe[e.to]=i;
						que.push(P(d[e.to],e.to));
					}
				}
			}
			if(d[t]==LINF) return flow;
			for(int i=0;i<n;i++) h[i]+=d[i];
			int dt=INF;
			for(int v=t;v!=s;v=pv[v]) dt=min(dt,vec[pv[v]][pe[v]].cap);
			flow+=(ll) dt*h[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);
	ll mx=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;
			mx=max(mx,cost);
		}
	}
	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;
			cost=max(cost,0LL);
			solve.add(i,j+sk,1,mx-cost);
		}
	}
	printf("%lld\n",sum+solve.min_cost(s,t)-mx*(ll) min(sk,sd));
	return 0;
}

Submission Info

Submission Time
Task H - Dungeon
User yutaka1999
Language C++ (G++ 4.6.4)
Score 100
Code Size 2621 Byte
Status AC
Exec Time 1441 ms
Memory 8808 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:86:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:87: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 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 84 ms 2760 KB
colorful1_02.txt AC 63 ms 2752 KB
colorful1_03.txt AC 84 ms 2756 KB
colorful2_01.txt AC 400 ms 8012 KB
colorful2_02.txt AC 280 ms 7928 KB
colorful2_03.txt AC 300 ms 7876 KB
colorful3_01.txt AC 543 ms 8232 KB
colorful3_02.txt AC 576 ms 8248 KB
colorful3_03.txt AC 1441 ms 8808 KB
corner_01.txt AC 28 ms 908 KB
corner_02.txt AC 27 ms 904 KB
corner_03.txt AC 27 ms 908 KB
corner_04.txt AC 41 ms 1492 KB
corner_05.txt AC 30 ms 892 KB
corner_06.txt AC 28 ms 836 KB
interval_01.txt AC 36 ms 1228 KB
interval_02.txt AC 276 ms 7756 KB
interval_03.txt AC 306 ms 7872 KB
interval_04.txt AC 109 ms 4528 KB
random_01.txt AC 312 ms 7868 KB
random_02.txt AC 363 ms 8000 KB
random_03.txt AC 281 ms 7880 KB
random_04.txt AC 325 ms 7872 KB
random_05.txt AC 322 ms 7868 KB
random_06.txt AC 320 ms 7868 KB
random_exp_01.txt AC 29 ms 1168 KB
random_exp_02.txt AC 27 ms 828 KB
random_exp_03.txt AC 27 ms 912 KB
random_max_01.txt AC 373 ms 7868 KB
random_max_02.txt AC 378 ms 8000 KB
random_max_03.txt AC 400 ms 8008 KB
random_max_04.txt AC 371 ms 7864 KB
random_max_05.txt AC 377 ms 7872 KB
random_max_06.txt AC 378 ms 8004 KB
random_max_07.txt AC 397 ms 8012 KB
random_max_08.txt AC 407 ms 8000 KB
random_max_09.txt AC 390 ms 8012 KB
random_max_10.txt AC 391 ms 8000 KB
random_select_01.txt AC 145 ms 4544 KB
random_select_02.txt AC 161 ms 4636 KB
random_select_03.txt AC 140 ms 4544 KB
random_select_04.txt AC 143 ms 4548 KB
random_select_05.txt AC 141 ms 4476 KB
random_select_06.txt AC 141 ms 4552 KB
random_select_07.txt AC 153 ms 4552 KB
random_select_08.txt AC 148 ms 4544 KB
random_select_09.txt AC 129 ms 4544 KB
random_select_10.txt AC 149 ms 4548 KB
random_small_01.txt AC 27 ms 908 KB
random_small_02.txt AC 27 ms 904 KB
random_small_03.txt AC 27 ms 836 KB
random_small_04.txt AC 34 ms 904 KB
random_small_05.txt AC 30 ms 1096 KB
random_small_06.txt AC 31 ms 1100 KB
random_small_07.txt AC 34 ms 1220 KB
random_small_08.txt AC 38 ms 1552 KB
random_small_09.txt AC 44 ms 1548 KB
random_small_10.txt AC 51 ms 1936 KB
sample_01.txt AC 27 ms 832 KB
sample_02.txt AC 27 ms 908 KB
sample_03.txt AC 27 ms 832 KB