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
2015-08-27 21:00:04+0900
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
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