# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
810721 |
2023-08-06T14:35:09 Z |
erray |
Wiring (IOI17_wiring) |
C++17 |
|
39 ms |
8468 KB |
#include "wiring.h"
//author: erray
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/debug.h"
#else
#define debug(...) (void) 37
#endif
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<vector<int>> gs;
{
vector<int> m;
merge(r.begin(), r.end(), b.begin(), b.end(), back_inserter(m));
int pr = -1, pb = -1;
int last = -1;
for (int i = 0; i < int(m.size()); ++i) {
int next = -1;
if (pr + 1 < int(r.size()) && r[pr + 1] == m[i]) {
++pr;
next = 0;
} else {
++pb;
next = 1;
}
if (next != last) {
gs.push_back({});
}
gs.back().push_back(m[i]);
swap(next, last);
}
}
debug(gs);
const long long inf = (long long) 1e17;
vector<long long> dp(int(gs[0].size()) + 1, inf);
dp[0] = 0;
for (int bi = 1; bi < int(gs.size()); ++bi) {
debug(dp);
auto& v = gs[bi];
auto& prev = gs[bi - 1];
int n = int(v.size());
int m = int(prev.size());
int gap = v[0] - prev.back();
vector<long long> small(n + 1, inf), big(n + 1, inf);
{
long long sum = 0;
for (int i = m - 1; i >= 0; --i) {
sum += prev[m - 1] - prev[i];
int match = m - i;
long long cost = sum + dp[i];
if (match <= n) {
big[match] = min(big[match], cost);
}
match = min(match, n);
small[match] = min(small[match], cost + 1LL * (m - i) * gap);
}
}
vector<long long> new_dp(n + 1);
{
long long mn = inf;
for (int i = 1; i <= n; ++i) {
mn = min(mn, big[i]);
new_dp[i] = mn + 1LL * i * gap;
}
}
{
long long mn = inf;
for (int i = n; i >= 1; --i) {
mn = min(mn, small[i]);
new_dp[i] = min(new_dp[i], mn);
}
}
new_dp[0] = dp[m];
{
long long sum = 0;
for (int i = 1; i <= n; ++i) {
sum += v[i - 1] - v[0];
new_dp[i] += sum;
}
}
swap(dp, new_dp);
for (int i = n; i > 0; --i) {
dp[i - 1] = min(dp[i], dp[i - 1]);
}
}
debug(dp);
return dp.back();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
16 ms |
5520 KB |
Output is correct |
4 |
Correct |
15 ms |
5500 KB |
Output is correct |
5 |
Correct |
16 ms |
6804 KB |
Output is correct |
6 |
Correct |
23 ms |
8460 KB |
Output is correct |
7 |
Correct |
21 ms |
8468 KB |
Output is correct |
8 |
Correct |
22 ms |
8364 KB |
Output is correct |
9 |
Correct |
22 ms |
8448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
32 ms |
7964 KB |
Output is correct |
4 |
Correct |
24 ms |
7320 KB |
Output is correct |
5 |
Correct |
0 ms |
300 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
29 ms |
7980 KB |
Output is correct |
19 |
Correct |
29 ms |
7996 KB |
Output is correct |
20 |
Correct |
26 ms |
7584 KB |
Output is correct |
21 |
Correct |
29 ms |
7976 KB |
Output is correct |
22 |
Correct |
28 ms |
7572 KB |
Output is correct |
23 |
Correct |
38 ms |
7572 KB |
Output is correct |
24 |
Correct |
39 ms |
7612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
18 ms |
4864 KB |
Output is correct |
3 |
Correct |
22 ms |
5920 KB |
Output is correct |
4 |
Correct |
18 ms |
5040 KB |
Output is correct |
5 |
Correct |
23 ms |
5928 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
296 KB |
Output is correct |
13 |
Correct |
0 ms |
304 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
300 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
18 ms |
5776 KB |
Output is correct |
19 |
Correct |
18 ms |
4776 KB |
Output is correct |
20 |
Correct |
21 ms |
5020 KB |
Output is correct |
21 |
Correct |
19 ms |
4908 KB |
Output is correct |
22 |
Correct |
21 ms |
6556 KB |
Output is correct |
23 |
Correct |
18 ms |
6548 KB |
Output is correct |
24 |
Correct |
19 ms |
6424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
16 ms |
5520 KB |
Output is correct |
20 |
Correct |
15 ms |
5500 KB |
Output is correct |
21 |
Correct |
16 ms |
6804 KB |
Output is correct |
22 |
Correct |
23 ms |
8460 KB |
Output is correct |
23 |
Correct |
21 ms |
8468 KB |
Output is correct |
24 |
Correct |
22 ms |
8364 KB |
Output is correct |
25 |
Correct |
22 ms |
8448 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
32 ms |
7964 KB |
Output is correct |
29 |
Correct |
24 ms |
7320 KB |
Output is correct |
30 |
Correct |
0 ms |
300 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
256 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
0 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
29 ms |
7980 KB |
Output is correct |
44 |
Correct |
29 ms |
7996 KB |
Output is correct |
45 |
Correct |
26 ms |
7584 KB |
Output is correct |
46 |
Correct |
29 ms |
7976 KB |
Output is correct |
47 |
Correct |
28 ms |
7572 KB |
Output is correct |
48 |
Correct |
38 ms |
7572 KB |
Output is correct |
49 |
Correct |
39 ms |
7612 KB |
Output is correct |
50 |
Correct |
0 ms |
212 KB |
Output is correct |
51 |
Correct |
18 ms |
4864 KB |
Output is correct |
52 |
Correct |
22 ms |
5920 KB |
Output is correct |
53 |
Correct |
18 ms |
5040 KB |
Output is correct |
54 |
Correct |
23 ms |
5928 KB |
Output is correct |
55 |
Correct |
0 ms |
212 KB |
Output is correct |
56 |
Correct |
0 ms |
212 KB |
Output is correct |
57 |
Correct |
0 ms |
212 KB |
Output is correct |
58 |
Correct |
0 ms |
212 KB |
Output is correct |
59 |
Correct |
0 ms |
212 KB |
Output is correct |
60 |
Correct |
0 ms |
212 KB |
Output is correct |
61 |
Correct |
0 ms |
296 KB |
Output is correct |
62 |
Correct |
0 ms |
304 KB |
Output is correct |
63 |
Correct |
0 ms |
212 KB |
Output is correct |
64 |
Correct |
1 ms |
300 KB |
Output is correct |
65 |
Correct |
0 ms |
212 KB |
Output is correct |
66 |
Correct |
0 ms |
212 KB |
Output is correct |
67 |
Correct |
18 ms |
5776 KB |
Output is correct |
68 |
Correct |
18 ms |
4776 KB |
Output is correct |
69 |
Correct |
21 ms |
5020 KB |
Output is correct |
70 |
Correct |
19 ms |
4908 KB |
Output is correct |
71 |
Correct |
21 ms |
6556 KB |
Output is correct |
72 |
Correct |
18 ms |
6548 KB |
Output is correct |
73 |
Correct |
19 ms |
6424 KB |
Output is correct |
74 |
Correct |
25 ms |
7708 KB |
Output is correct |
75 |
Correct |
19 ms |
6156 KB |
Output is correct |
76 |
Correct |
22 ms |
6048 KB |
Output is correct |
77 |
Correct |
19 ms |
6420 KB |
Output is correct |
78 |
Correct |
20 ms |
6936 KB |
Output is correct |
79 |
Correct |
20 ms |
6296 KB |
Output is correct |
80 |
Correct |
19 ms |
6108 KB |
Output is correct |
81 |
Correct |
19 ms |
6716 KB |
Output is correct |
82 |
Correct |
19 ms |
6432 KB |
Output is correct |
83 |
Correct |
24 ms |
6412 KB |
Output is correct |
84 |
Correct |
22 ms |
6556 KB |
Output is correct |
85 |
Correct |
21 ms |
6160 KB |
Output is correct |
86 |
Correct |
22 ms |
7192 KB |
Output is correct |
87 |
Correct |
22 ms |
6840 KB |
Output is correct |
88 |
Correct |
20 ms |
6200 KB |
Output is correct |
89 |
Correct |
22 ms |
6576 KB |
Output is correct |
90 |
Correct |
21 ms |
6800 KB |
Output is correct |
91 |
Correct |
21 ms |
6920 KB |
Output is correct |
92 |
Correct |
22 ms |
6928 KB |
Output is correct |
93 |
Correct |
21 ms |
6812 KB |
Output is correct |
94 |
Correct |
22 ms |
7580 KB |
Output is correct |
95 |
Correct |
29 ms |
6540 KB |
Output is correct |
96 |
Correct |
29 ms |
7052 KB |
Output is correct |
97 |
Correct |
21 ms |
8172 KB |
Output is correct |
98 |
Correct |
22 ms |
7584 KB |
Output is correct |
99 |
Correct |
21 ms |
7572 KB |
Output is correct |
100 |
Correct |
21 ms |
7056 KB |
Output is correct |
101 |
Correct |
22 ms |
7684 KB |
Output is correct |
102 |
Correct |
21 ms |
6188 KB |
Output is correct |