Submission #478138
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;
while(1)
{
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:43:13+0900
Task
H - Dungeon
User
yutaka1999
Language
C++ (G++ 4.6.4)
Score
0
Code Size
2252 Byte
Status
TLE
Exec Time
5037 ms
Memory
6128 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
64 ms
1516 KB
colorful1_02.txt
AC
38 ms
1056 KB
colorful1_03.txt
AC
71 ms
1556 KB
colorful2_01.txt
AC
490 ms
3564 KB
colorful2_02.txt
AC
40 ms
1304 KB
colorful2_03.txt
AC
92 ms
1820 KB
colorful3_01.txt
AC
232 ms
3176 KB
colorful3_02.txt
AC
261 ms
3176 KB
colorful3_03.txt
AC
622 ms
6128 KB
corner_01.txt
AC
26 ms
916 KB
corner_02.txt
AC
27 ms
880 KB
corner_03.txt
AC
25 ms
916 KB
corner_04.txt
AC
27 ms
920 KB
corner_05.txt
AC
26 ms
924 KB
corner_06.txt
AC
26 ms
928 KB
interval_01.txt
AC
49 ms
1068 KB
interval_02.txt
AC
40 ms
1560 KB
interval_03.txt
AC
164 ms
3052 KB
interval_04.txt
AC
60 ms
1952 KB
random_01.txt
AC
117 ms
2416 KB
random_02.txt
AC
210 ms
3044 KB
random_03.txt
AC
63 ms
1820 KB
random_04.txt
AC
215 ms
3312 KB
random_05.txt
AC
175 ms
3056 KB
random_06.txt
AC
165 ms
3184 KB
random_exp_01.txt
AC
26 ms
1180 KB
random_exp_02.txt
TLE
5037 ms
944 KB
random_exp_03.txt
AC
26 ms
924 KB
random_max_01.txt
AC
378 ms
3432 KB
random_max_02.txt
AC
391 ms
3692 KB
random_max_03.txt
AC
529 ms
3692 KB
random_max_04.txt
AC
379 ms
3564 KB
random_max_05.txt
AC
440 ms
3432 KB
random_max_06.txt
AC
455 ms
3496 KB
random_max_07.txt
AC
468 ms
3560 KB
random_max_08.txt
AC
479 ms
3556 KB
random_max_09.txt
AC
400 ms
3432 KB
random_max_10.txt
AC
384 ms
3688 KB
random_select_01.txt
AC
274 ms
2576 KB
random_select_02.txt
AC
226 ms
2548 KB
random_select_03.txt
AC
209 ms
2412 KB
random_select_04.txt
AC
185 ms
2284 KB
random_select_05.txt
AC
185 ms
2276 KB
random_select_06.txt
AC
240 ms
2416 KB
random_select_07.txt
AC
281 ms
2404 KB
random_select_08.txt
AC
236 ms
2720 KB
random_select_09.txt
AC
175 ms
2288 KB
random_select_10.txt
AC
229 ms
2456 KB
random_small_01.txt
AC
28 ms
872 KB
random_small_02.txt
AC
27 ms
872 KB
random_small_03.txt
AC
27 ms
924 KB
random_small_04.txt
AC
25 ms
920 KB
random_small_05.txt
AC
29 ms
1048 KB
random_small_06.txt
AC
35 ms
948 KB
random_small_07.txt
AC
31 ms
1052 KB
random_small_08.txt
AC
35 ms
1176 KB
random_small_09.txt
AC
45 ms
1256 KB
random_small_10.txt
AC
45 ms
1304 KB
sample_01.txt
AC
25 ms
872 KB
sample_02.txt
AC
26 ms
880 KB
sample_03.txt
AC
27 ms
924 KB