# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
419941 |
2021-06-07T19:12:25 Z |
Blagojce |
Wiring (IOI17_wiring) |
C++11 |
|
86 ms |
13596 KB |
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 5e5+5;
#include "wiring.h"
long long min_total_length(std::vector<int> r, std::vector<int> b){
vector<pair<int, int> > v;
for(auto u : r) v.pb({u, 0});
for(auto u : b) v.pb({u, 1});
sort(all(v));
int n = (int)v.size();
vector<vector<ll> > g;
int col = -1;
fr(i, 0, n){
if(v[i].nd != col) g.pb({});
g.back().pb(v[i].st);
col = v[i].nd;
}
int m = g.size();
vector<ll> dp[m];
ll s = 0;
fr(i, 0, (int)g[0].size()){
s += g[1][0] - g[0][i];
dp[0].pb(s);
}
reverse(all(dp[0]));
dp[0].pb(0);
fr(i, 1, m){
int s1 = g[i].size();
ll pref[s1+1];
pref[0] = 0;
s = 0;
fr(j, 0, s1){
s += g[i][j];
pref[j+1] = s;
}
int s2 = g[i-1].size();
ll suff[s2+1];
suff[0] = 0;
s = 0;
fr(j, 0, s2){
s += g[i-1][s2 - j - 1];
suff[j+1] = s;
}
dp[i].resize(s1+1);
fr(j, 0, s1+1) dp[i][j] = inf;
fr(j, 0, min(s1, s2) + 1){
ll cost = pref[j] - suff[j];
dp[i][s1-j] = dp[i-1][j] + cost;
}
if(i + 1 < m){
for(int j = s1; j >= 1; j --){
dp[i][j-1] = min(dp[i][j-1], dp[i][j] + min(g[i+1][0] - g[i][s1 - j], g[i][s1-j] - g[i-1].back()));
}
}
}
int lsz = (int)g.back().size();
ll ans = dp[m-1][0];
ll add = 0;
fr(i, 0, lsz){
add += g[m-1][lsz-i-1] - g[m-2].back();
ans = min(ans, dp[m-1][i+1] + add);
}
return ans;
}
/*
int main(){
cout<<min_total_length({1, 2, 3}, {6, 10});
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
30 ms |
7280 KB |
Output is correct |
4 |
Correct |
38 ms |
7220 KB |
Output is correct |
5 |
Correct |
33 ms |
7012 KB |
Output is correct |
6 |
Correct |
43 ms |
8824 KB |
Output is correct |
7 |
Correct |
39 ms |
8876 KB |
Output is correct |
8 |
Correct |
40 ms |
8868 KB |
Output is correct |
9 |
Correct |
40 ms |
8884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
70 ms |
11824 KB |
Output is correct |
4 |
Correct |
62 ms |
11236 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
86 ms |
13596 KB |
Output is correct |
19 |
Correct |
68 ms |
13576 KB |
Output is correct |
20 |
Correct |
64 ms |
11552 KB |
Output is correct |
21 |
Correct |
76 ms |
13576 KB |
Output is correct |
22 |
Correct |
83 ms |
12948 KB |
Output is correct |
23 |
Correct |
67 ms |
12940 KB |
Output is correct |
24 |
Correct |
66 ms |
12984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
43 ms |
6948 KB |
Output is correct |
3 |
Correct |
55 ms |
9908 KB |
Output is correct |
4 |
Correct |
47 ms |
8500 KB |
Output is correct |
5 |
Correct |
53 ms |
9912 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
296 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
48 ms |
8992 KB |
Output is correct |
19 |
Correct |
45 ms |
8004 KB |
Output is correct |
20 |
Correct |
44 ms |
8272 KB |
Output is correct |
21 |
Correct |
41 ms |
8320 KB |
Output is correct |
22 |
Correct |
47 ms |
9740 KB |
Output is correct |
23 |
Correct |
43 ms |
9524 KB |
Output is correct |
24 |
Correct |
41 ms |
9752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
30 ms |
7280 KB |
Output is correct |
20 |
Correct |
38 ms |
7220 KB |
Output is correct |
21 |
Correct |
33 ms |
7012 KB |
Output is correct |
22 |
Correct |
43 ms |
8824 KB |
Output is correct |
23 |
Correct |
39 ms |
8876 KB |
Output is correct |
24 |
Correct |
40 ms |
8868 KB |
Output is correct |
25 |
Correct |
40 ms |
8884 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
0 ms |
204 KB |
Output is correct |
28 |
Correct |
70 ms |
11824 KB |
Output is correct |
29 |
Correct |
62 ms |
11236 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
296 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
1 ms |
296 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
1 ms |
204 KB |
Output is correct |
40 |
Correct |
1 ms |
204 KB |
Output is correct |
41 |
Correct |
1 ms |
296 KB |
Output is correct |
42 |
Correct |
1 ms |
204 KB |
Output is correct |
43 |
Correct |
86 ms |
13596 KB |
Output is correct |
44 |
Correct |
68 ms |
13576 KB |
Output is correct |
45 |
Correct |
64 ms |
11552 KB |
Output is correct |
46 |
Correct |
76 ms |
13576 KB |
Output is correct |
47 |
Correct |
83 ms |
12948 KB |
Output is correct |
48 |
Correct |
67 ms |
12940 KB |
Output is correct |
49 |
Correct |
66 ms |
12984 KB |
Output is correct |
50 |
Correct |
0 ms |
204 KB |
Output is correct |
51 |
Correct |
43 ms |
6948 KB |
Output is correct |
52 |
Correct |
55 ms |
9908 KB |
Output is correct |
53 |
Correct |
47 ms |
8500 KB |
Output is correct |
54 |
Correct |
53 ms |
9912 KB |
Output is correct |
55 |
Correct |
1 ms |
204 KB |
Output is correct |
56 |
Correct |
1 ms |
204 KB |
Output is correct |
57 |
Correct |
1 ms |
204 KB |
Output is correct |
58 |
Correct |
1 ms |
204 KB |
Output is correct |
59 |
Correct |
1 ms |
204 KB |
Output is correct |
60 |
Correct |
1 ms |
204 KB |
Output is correct |
61 |
Correct |
1 ms |
296 KB |
Output is correct |
62 |
Correct |
1 ms |
204 KB |
Output is correct |
63 |
Correct |
1 ms |
204 KB |
Output is correct |
64 |
Correct |
1 ms |
204 KB |
Output is correct |
65 |
Correct |
1 ms |
204 KB |
Output is correct |
66 |
Correct |
1 ms |
204 KB |
Output is correct |
67 |
Correct |
48 ms |
8992 KB |
Output is correct |
68 |
Correct |
45 ms |
8004 KB |
Output is correct |
69 |
Correct |
44 ms |
8272 KB |
Output is correct |
70 |
Correct |
41 ms |
8320 KB |
Output is correct |
71 |
Correct |
47 ms |
9740 KB |
Output is correct |
72 |
Correct |
43 ms |
9524 KB |
Output is correct |
73 |
Correct |
41 ms |
9752 KB |
Output is correct |
74 |
Correct |
41 ms |
10640 KB |
Output is correct |
75 |
Correct |
47 ms |
9012 KB |
Output is correct |
76 |
Correct |
46 ms |
9580 KB |
Output is correct |
77 |
Correct |
45 ms |
8988 KB |
Output is correct |
78 |
Correct |
52 ms |
9352 KB |
Output is correct |
79 |
Correct |
44 ms |
9116 KB |
Output is correct |
80 |
Correct |
39 ms |
9396 KB |
Output is correct |
81 |
Correct |
43 ms |
9848 KB |
Output is correct |
82 |
Correct |
40 ms |
9620 KB |
Output is correct |
83 |
Correct |
51 ms |
9508 KB |
Output is correct |
84 |
Correct |
41 ms |
10292 KB |
Output is correct |
85 |
Correct |
50 ms |
9452 KB |
Output is correct |
86 |
Correct |
43 ms |
10524 KB |
Output is correct |
87 |
Correct |
43 ms |
9780 KB |
Output is correct |
88 |
Correct |
49 ms |
9524 KB |
Output is correct |
89 |
Correct |
53 ms |
9624 KB |
Output is correct |
90 |
Correct |
51 ms |
9652 KB |
Output is correct |
91 |
Correct |
43 ms |
10012 KB |
Output is correct |
92 |
Correct |
47 ms |
9496 KB |
Output is correct |
93 |
Correct |
42 ms |
9876 KB |
Output is correct |
94 |
Correct |
44 ms |
9880 KB |
Output is correct |
95 |
Correct |
47 ms |
9648 KB |
Output is correct |
96 |
Correct |
50 ms |
10000 KB |
Output is correct |
97 |
Correct |
54 ms |
10332 KB |
Output is correct |
98 |
Correct |
44 ms |
10164 KB |
Output is correct |
99 |
Correct |
43 ms |
10132 KB |
Output is correct |
100 |
Correct |
47 ms |
9720 KB |
Output is correct |
101 |
Correct |
43 ms |
10096 KB |
Output is correct |
102 |
Correct |
48 ms |
9628 KB |
Output is correct |