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
2015-08-27 20:45:46+0900
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
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