# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
513739 | 2022-01-17T13:23:49 Z | AdamGS | Wiring (IOI17_wiring) | C++17 | 95 ms | 29212 KB |
#include "wiring.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e5+7; const ll INF=1e9+7; vector<ll>V[LIM], dp[LIM], midp[LIM]; vector<pair<int,int>>T; int n; long long min_total_length(vector<int>R, vector<int>B) { for(auto i : R) T.pb({i, 0}); for(auto i : B) T.pb({i, 1}); sort(all(T)); V[0].pb(T[0].st); for(int i=1; i<T.size(); ++i) { if(T[i].nd!=T[i-1].nd) ++n; V[n].pb(T[i].st); } ++n; V[n].pb(2*INF); ll sum=0; for(auto i : V[0]) sum+=V[1][0]-i; rep(i, V[0].size()+1) { dp[0].pb(sum); midp[0].pb(sum); } for(int i=1; i<n; ++i) { sum=0; for(auto j : V[i]) sum+=V[i+1][0]-j; ll akt=dp[i-1][dp[i-1].size()-1]; dp[i].pb(sum+midp[i-1].back()); rep(j, V[i].size()) { sum-=V[i+1][0]-V[i][j]; sum+=V[i][j]-V[i][0]; if(j<dp[i-1].size()) akt=min(akt, dp[i-1][dp[i-1].size()-j-1]); akt+=V[i][0]-V[i-1][V[i-1].size()-1]; dp[i].pb(sum+akt); if(j<=midp[i-1].size()-2) { dp[i][dp[i].size()-1]=min(dp[i][dp[i].size()-1], sum+midp[i-1][midp[i-1].size()-j-2]); } } midp[i].pb(dp[i][0]); for(int j=1; j<dp[i].size(); ++j) midp[i].pb(min(midp[i][midp[i].size()-1], dp[i][j])); } return dp[n-1].back(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14284 KB | Output is correct |
2 | Correct | 8 ms | 14284 KB | Output is correct |
3 | Correct | 7 ms | 14384 KB | Output is correct |
4 | Correct | 8 ms | 14412 KB | Output is correct |
5 | Correct | 8 ms | 14284 KB | Output is correct |
6 | Correct | 7 ms | 14284 KB | Output is correct |
7 | Correct | 8 ms | 14384 KB | Output is correct |
8 | Correct | 11 ms | 14300 KB | Output is correct |
9 | Correct | 8 ms | 14384 KB | Output is correct |
10 | Correct | 8 ms | 14364 KB | Output is correct |
11 | Correct | 7 ms | 14412 KB | Output is correct |
12 | Correct | 8 ms | 14384 KB | Output is correct |
13 | Correct | 10 ms | 14300 KB | Output is correct |
14 | Correct | 8 ms | 14412 KB | Output is correct |
15 | Correct | 8 ms | 14412 KB | Output is correct |
16 | Correct | 8 ms | 14364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14372 KB | Output is correct |
2 | Correct | 8 ms | 14380 KB | Output is correct |
3 | Correct | 36 ms | 22796 KB | Output is correct |
4 | Correct | 33 ms | 22744 KB | Output is correct |
5 | Correct | 34 ms | 23096 KB | Output is correct |
6 | Correct | 40 ms | 25632 KB | Output is correct |
7 | Correct | 39 ms | 25596 KB | Output is correct |
8 | Correct | 41 ms | 25628 KB | Output is correct |
9 | Correct | 41 ms | 25616 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 14308 KB | Output is correct |
2 | Correct | 10 ms | 14384 KB | Output is correct |
3 | Correct | 95 ms | 29212 KB | Output is correct |
4 | Correct | 59 ms | 26932 KB | Output is correct |
5 | Correct | 8 ms | 14384 KB | Output is correct |
6 | Correct | 8 ms | 14380 KB | Output is correct |
7 | Correct | 7 ms | 14388 KB | Output is correct |
8 | Correct | 8 ms | 14384 KB | Output is correct |
9 | Correct | 9 ms | 14388 KB | Output is correct |
10 | Correct | 7 ms | 14284 KB | Output is correct |
11 | Correct | 8 ms | 14284 KB | Output is correct |
12 | Correct | 8 ms | 14284 KB | Output is correct |
13 | Correct | 7 ms | 14388 KB | Output is correct |
14 | Correct | 7 ms | 14376 KB | Output is correct |
15 | Correct | 7 ms | 14284 KB | Output is correct |
16 | Correct | 8 ms | 14284 KB | Output is correct |
17 | Correct | 8 ms | 14396 KB | Output is correct |
18 | Correct | 70 ms | 29176 KB | Output is correct |
19 | Correct | 85 ms | 29208 KB | Output is correct |
20 | Correct | 69 ms | 27296 KB | Output is correct |
21 | Correct | 70 ms | 29212 KB | Output is correct |
22 | Correct | 69 ms | 28816 KB | Output is correct |
23 | Correct | 78 ms | 28784 KB | Output is correct |
24 | Correct | 81 ms | 28832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 14284 KB | Output is correct |
2 | Correct | 49 ms | 24224 KB | Output is correct |
3 | Correct | 64 ms | 26676 KB | Output is correct |
4 | Correct | 47 ms | 25228 KB | Output is correct |
5 | Correct | 56 ms | 26664 KB | Output is correct |
6 | Correct | 7 ms | 14384 KB | Output is correct |
7 | Correct | 9 ms | 14412 KB | Output is correct |
8 | Correct | 10 ms | 14412 KB | Output is correct |
9 | Correct | 7 ms | 14284 KB | Output is correct |
10 | Correct | 8 ms | 14380 KB | Output is correct |
11 | Correct | 7 ms | 14284 KB | Output is correct |
12 | Correct | 7 ms | 14392 KB | Output is correct |
13 | Correct | 7 ms | 14284 KB | Output is correct |
14 | Correct | 7 ms | 14284 KB | Output is correct |
15 | Correct | 7 ms | 14284 KB | Output is correct |
16 | Correct | 7 ms | 14384 KB | Output is correct |
17 | Correct | 7 ms | 14284 KB | Output is correct |
18 | Correct | 40 ms | 24096 KB | Output is correct |
19 | Correct | 48 ms | 24096 KB | Output is correct |
20 | Correct | 45 ms | 24792 KB | Output is correct |
21 | Correct | 39 ms | 24100 KB | Output is correct |
22 | Correct | 42 ms | 24652 KB | Output is correct |
23 | Correct | 41 ms | 24452 KB | Output is correct |
24 | Correct | 50 ms | 24664 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14284 KB | Output is correct |
2 | Correct | 8 ms | 14284 KB | Output is correct |
3 | Correct | 7 ms | 14384 KB | Output is correct |
4 | Correct | 8 ms | 14412 KB | Output is correct |
5 | Correct | 8 ms | 14284 KB | Output is correct |
6 | Correct | 7 ms | 14284 KB | Output is correct |
7 | Correct | 8 ms | 14384 KB | Output is correct |
8 | Correct | 11 ms | 14300 KB | Output is correct |
9 | Correct | 8 ms | 14384 KB | Output is correct |
10 | Correct | 8 ms | 14364 KB | Output is correct |
11 | Correct | 7 ms | 14412 KB | Output is correct |
12 | Correct | 8 ms | 14384 KB | Output is correct |
13 | Correct | 10 ms | 14300 KB | Output is correct |
14 | Correct | 8 ms | 14412 KB | Output is correct |
15 | Correct | 8 ms | 14412 KB | Output is correct |
16 | Correct | 8 ms | 14364 KB | Output is correct |
17 | Correct | 8 ms | 14372 KB | Output is correct |
18 | Correct | 8 ms | 14380 KB | Output is correct |
19 | Correct | 36 ms | 22796 KB | Output is correct |
20 | Correct | 33 ms | 22744 KB | Output is correct |
21 | Correct | 34 ms | 23096 KB | Output is correct |
22 | Correct | 40 ms | 25632 KB | Output is correct |
23 | Correct | 39 ms | 25596 KB | Output is correct |
24 | Correct | 41 ms | 25628 KB | Output is correct |
25 | Correct | 41 ms | 25616 KB | Output is correct |
26 | Correct | 10 ms | 14308 KB | Output is correct |
27 | Correct | 10 ms | 14384 KB | Output is correct |
28 | Correct | 95 ms | 29212 KB | Output is correct |
29 | Correct | 59 ms | 26932 KB | Output is correct |
30 | Correct | 8 ms | 14384 KB | Output is correct |
31 | Correct | 8 ms | 14380 KB | Output is correct |
32 | Correct | 7 ms | 14388 KB | Output is correct |
33 | Correct | 8 ms | 14384 KB | Output is correct |
34 | Correct | 9 ms | 14388 KB | Output is correct |
35 | Correct | 7 ms | 14284 KB | Output is correct |
36 | Correct | 8 ms | 14284 KB | Output is correct |
37 | Correct | 8 ms | 14284 KB | Output is correct |
38 | Correct | 7 ms | 14388 KB | Output is correct |
39 | Correct | 7 ms | 14376 KB | Output is correct |
40 | Correct | 7 ms | 14284 KB | Output is correct |
41 | Correct | 8 ms | 14284 KB | Output is correct |
42 | Correct | 8 ms | 14396 KB | Output is correct |
43 | Correct | 70 ms | 29176 KB | Output is correct |
44 | Correct | 85 ms | 29208 KB | Output is correct |
45 | Correct | 69 ms | 27296 KB | Output is correct |
46 | Correct | 70 ms | 29212 KB | Output is correct |
47 | Correct | 69 ms | 28816 KB | Output is correct |
48 | Correct | 78 ms | 28784 KB | Output is correct |
49 | Correct | 81 ms | 28832 KB | Output is correct |
50 | Correct | 7 ms | 14284 KB | Output is correct |
51 | Correct | 49 ms | 24224 KB | Output is correct |
52 | Correct | 64 ms | 26676 KB | Output is correct |
53 | Correct | 47 ms | 25228 KB | Output is correct |
54 | Correct | 56 ms | 26664 KB | Output is correct |
55 | Correct | 7 ms | 14384 KB | Output is correct |
56 | Correct | 9 ms | 14412 KB | Output is correct |
57 | Correct | 10 ms | 14412 KB | Output is correct |
58 | Correct | 7 ms | 14284 KB | Output is correct |
59 | Correct | 8 ms | 14380 KB | Output is correct |
60 | Correct | 7 ms | 14284 KB | Output is correct |
61 | Correct | 7 ms | 14392 KB | Output is correct |
62 | Correct | 7 ms | 14284 KB | Output is correct |
63 | Correct | 7 ms | 14284 KB | Output is correct |
64 | Correct | 7 ms | 14284 KB | Output is correct |
65 | Correct | 7 ms | 14384 KB | Output is correct |
66 | Correct | 7 ms | 14284 KB | Output is correct |
67 | Correct | 40 ms | 24096 KB | Output is correct |
68 | Correct | 48 ms | 24096 KB | Output is correct |
69 | Correct | 45 ms | 24792 KB | Output is correct |
70 | Correct | 39 ms | 24100 KB | Output is correct |
71 | Correct | 42 ms | 24652 KB | Output is correct |
72 | Correct | 41 ms | 24452 KB | Output is correct |
73 | Correct | 50 ms | 24664 KB | Output is correct |
74 | Correct | 39 ms | 25124 KB | Output is correct |
75 | Correct | 44 ms | 24728 KB | Output is correct |
76 | Correct | 48 ms | 25272 KB | Output is correct |
77 | Correct | 51 ms | 24220 KB | Output is correct |
78 | Correct | 41 ms | 24728 KB | Output is correct |
79 | Correct | 43 ms | 24612 KB | Output is correct |
80 | Correct | 37 ms | 24740 KB | Output is correct |
81 | Correct | 47 ms | 25668 KB | Output is correct |
82 | Correct | 39 ms | 24476 KB | Output is correct |
83 | Correct | 41 ms | 25396 KB | Output is correct |
84 | Correct | 39 ms | 25496 KB | Output is correct |
85 | Correct | 47 ms | 24856 KB | Output is correct |
86 | Correct | 42 ms | 25872 KB | Output is correct |
87 | Correct | 40 ms | 25108 KB | Output is correct |
88 | Correct | 42 ms | 24868 KB | Output is correct |
89 | Correct | 41 ms | 24476 KB | Output is correct |
90 | Correct | 54 ms | 24884 KB | Output is correct |
91 | Correct | 42 ms | 25124 KB | Output is correct |
92 | Correct | 43 ms | 25236 KB | Output is correct |
93 | Correct | 43 ms | 25024 KB | Output is correct |
94 | Correct | 42 ms | 24864 KB | Output is correct |
95 | Correct | 46 ms | 24464 KB | Output is correct |
96 | Correct | 43 ms | 25104 KB | Output is correct |
97 | Correct | 42 ms | 25508 KB | Output is correct |
98 | Correct | 42 ms | 25244 KB | Output is correct |
99 | Correct | 42 ms | 25236 KB | Output is correct |
100 | Correct | 49 ms | 24864 KB | Output is correct |
101 | Correct | 47 ms | 25488 KB | Output is correct |
102 | Correct | 48 ms | 24852 KB | Output is correct |