| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831473 |
2023-08-20T09:33:49 Z |
WLZ |
Wiring (IOI17_wiring) |
C++17 |
|
1000 ms |
8124 KB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LINF = (ll) 1e18;
long long min_total_length(std::vector<int> a, std::vector<int> b) {
int n = (int) a.size(), m = (int) b.size();
vector< pair<int, int> > v;
for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
sort(v.begin(), v.end());
v.insert(v.begin(), {0, -1});
vector<int> seg(n + m + 1); seg[1] = 0; seg[0] = -5;
vector<int> sz;
int len = 1;
for (int i = 2; i <= n + m; i++) {
seg[i] = seg[i - 1];
len++;
if (v[i].second != v[i - 1].second) {
sz.push_back(len - 1);
seg[i]++, len = 1;
}
}
sz.push_back(len);
vector<ll> dp(n + m + 1, LINF); dp[0] = 0;
for (int i = 1; i <= n + m; i++) {
if (seg[i] == 0) continue;
int cnt_l = 0, cnt_r = 0;
ll sum_l = 0, sum_r = 0;
ll last_l = 0, last_r = -1;
for (int j = i - 1; j >= 0; j--) {
if (seg[j + 1] == seg[i]) {
cnt_l++; sum_l += v[j + 1].first;
last_l = v[j + 1].first;
}
if (seg[j + 1] == seg[i] - 1) {
cnt_r++; sum_r += v[j + 1].first;
if (last_r == -1) last_r = v[j + 1].first;
}
if (cnt_r > 0) {
ll add = sum_l - sum_r;
if (cnt_l > cnt_r) add -= last_r * (cnt_l - cnt_r);
else add += last_l * (cnt_r - cnt_l);
dp[i] = min(dp[i], dp[j + 1] + add);
dp[i] = min(dp[i], dp[j] + add);
}
if (seg[j] < seg[i] - 1) break;
}
}
return dp[n + m];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
260 KB |
Output is correct |
| 13 |
Correct |
1 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
1093 ms |
4340 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
38 ms |
6264 KB |
Output is correct |
| 4 |
Correct |
38 ms |
7708 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
36 ms |
8124 KB |
Output is correct |
| 19 |
Correct |
36 ms |
8092 KB |
Output is correct |
| 20 |
Correct |
39 ms |
8092 KB |
Output is correct |
| 21 |
Correct |
36 ms |
8100 KB |
Output is correct |
| 22 |
Correct |
37 ms |
8124 KB |
Output is correct |
| 23 |
Correct |
38 ms |
8092 KB |
Output is correct |
| 24 |
Correct |
38 ms |
8056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1086 ms |
5688 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
260 KB |
Output is correct |
| 13 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
| 19 |
Execution timed out |
1093 ms |
4340 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
