Submission #596482
Source Code Expand
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAXN = 2010; const int MAXM = 1000000; const long long INF = 100000000000000000LL; struct Edge { int to,next,cap,flow; long long cost; }edge[MAXM]; int head[MAXN],tol; int pre[MAXN]; long long dis[MAXN]; bool vis[MAXN]; int N;//节点总个数,节点编号从0~N-1 void init(int n) { N = n; tol = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int cap,long long cost) { edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } bool spfa(int s,int t) { queue<int>q; for(int i = 0;i < N;i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i != -1;i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(pre[t] == -1)return false; else return true; } //返回的是最大流,cost存的是最小费用 int minCostMaxflow(int s,int t,long long &cost) { int flow = 0; cost = 0; while(spfa(s,t)) { long long Min = INF; for(int i = pre[t];i != -1;i = pre[edge[i^1].to]) { if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for(int i = pre[t];i != -1;i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow; } pair<int,int>p[1000]; pair<int,int>da[1000]; pair<int,int>de[1000]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while(scanf("%d",&n) == 1) { for(int i = 0;i < n;i++) { scanf("%d%d", &p[i].first, &p[i].second); } long long sum = 0; int num1 = 0; int num2 = 0; int cnt = 0; for (int i = n-1;i >= 0;i--) { if (p[i].first == 2) { sum += p[i].second; cnt++; } else if (p[i].first == 0) { da[num1++] = make_pair(cnt, p[i].second); } else { de[num2++] = make_pair(cnt, p[i].second); } } init(num1+num2+2); for (int i = 1;i <= num1;i++)addedge(0,i,1,0); for (int i = num1+1;i <= num1+num2;i++)addedge(i,num1+num2+1,1,0); for (int i = 0;i < num1;i++) for(int j = 0;j < num2;j++) { long long cost = (long long)min(da[i].first, de[j].first)*de[j].second - da[i].second; if (cost < 0)cost = 0; addedge(i+1, num1+1+j, 1, -cost); } long long tmp; minCostMaxflow(0, num1+num2+1, tmp); long long ans = sum + tmp; printf("%lld\n",ans); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Dungeon |
User | kuangbin |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 3570 Byte |
Status | AC |
Exec Time | 2422 ms |
Memory | 5220 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:120:44: 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 | 220 ms | 2032 KB |
colorful1_02.txt | AC | 152 ms | 1964 KB |
colorful1_03.txt | AC | 216 ms | 2004 KB |
colorful2_01.txt | AC | 2199 ms | 5164 KB |
colorful2_02.txt | AC | 1289 ms | 5160 KB |
colorful2_03.txt | AC | 1412 ms | 5160 KB |
colorful3_01.txt | AC | 1267 ms | 5168 KB |
colorful3_02.txt | AC | 1145 ms | 5164 KB |
colorful3_03.txt | AC | 1057 ms | 5164 KB |
corner_01.txt | AC | 25 ms | 880 KB |
corner_02.txt | AC | 25 ms | 1048 KB |
corner_03.txt | AC | 24 ms | 980 KB |
corner_04.txt | AC | 53 ms | 1368 KB |
corner_05.txt | AC | 25 ms | 1040 KB |
corner_06.txt | AC | 25 ms | 1044 KB |
interval_01.txt | AC | 30 ms | 1304 KB |
interval_02.txt | AC | 1105 ms | 5164 KB |
interval_03.txt | AC | 1314 ms | 5156 KB |
interval_04.txt | AC | 307 ms | 2976 KB |
random_01.txt | AC | 1434 ms | 5168 KB |
random_02.txt | AC | 1414 ms | 5156 KB |
random_03.txt | AC | 1157 ms | 5164 KB |
random_04.txt | AC | 1058 ms | 5156 KB |
random_05.txt | AC | 1230 ms | 5112 KB |
random_06.txt | AC | 1044 ms | 5156 KB |
random_exp_01.txt | AC | 26 ms | 1064 KB |
random_exp_02.txt | AC | 25 ms | 1044 KB |
random_exp_03.txt | AC | 26 ms | 1048 KB |
random_max_01.txt | AC | 1964 ms | 5164 KB |
random_max_02.txt | AC | 1839 ms | 5160 KB |
random_max_03.txt | AC | 2375 ms | 5220 KB |
random_max_04.txt | AC | 1529 ms | 5160 KB |
random_max_05.txt | AC | 1925 ms | 5160 KB |
random_max_06.txt | AC | 1930 ms | 5164 KB |
random_max_07.txt | AC | 2422 ms | 5160 KB |
random_max_08.txt | AC | 2280 ms | 5160 KB |
random_max_09.txt | AC | 1809 ms | 5164 KB |
random_max_10.txt | AC | 1595 ms | 5160 KB |
random_select_01.txt | AC | 722 ms | 3096 KB |
random_select_02.txt | AC | 610 ms | 2988 KB |
random_select_03.txt | AC | 503 ms | 3096 KB |
random_select_04.txt | AC | 667 ms | 3092 KB |
random_select_05.txt | AC | 509 ms | 3104 KB |
random_select_06.txt | AC | 582 ms | 3096 KB |
random_select_07.txt | AC | 725 ms | 3092 KB |
random_select_08.txt | AC | 563 ms | 3116 KB |
random_select_09.txt | AC | 464 ms | 3116 KB |
random_select_10.txt | AC | 638 ms | 2988 KB |
random_small_01.txt | AC | 25 ms | 1044 KB |
random_small_02.txt | AC | 26 ms | 1048 KB |
random_small_03.txt | AC | 26 ms | 1048 KB |
random_small_04.txt | AC | 25 ms | 1048 KB |
random_small_05.txt | AC | 31 ms | 1048 KB |
random_small_06.txt | AC | 32 ms | 1064 KB |
random_small_07.txt | AC | 37 ms | 1308 KB |
random_small_08.txt | AC | 53 ms | 1320 KB |
random_small_09.txt | AC | 68 ms | 1324 KB |
random_small_10.txt | AC | 86 ms | 1460 KB |
sample_01.txt | AC | 26 ms | 1040 KB |
sample_02.txt | AC | 26 ms | 856 KB |
sample_03.txt | AC | 26 ms | 856 KB |