# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
903886 | 2024-01-11T13:24:52 Z | math_rabbit_1028 | Wiring (IOI17_wiring) | C++14 | 36 ms | 8756 KB |
#include <bits/stdc++.h> #include "wiring.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; vector<pii> arr; vector<ll> sum; vector<ll> dp; ll min_total_length(vector<int> R, vector<int> B) { arr.push_back({0, 0}); for (int i = 0; i < R.size(); i++) arr.push_back({R[i], 0}); for (int i = 0; i < B.size(); i++) arr.push_back({B[i], 1}); sort(arr.begin() + 1, arr.end()); dp = vector<ll>(arr.size(), 1e18); sum = vector<ll>(arr.size(), 0); for (int i = 1; i < sum.size(); i++) sum[i] = sum[i - 1] + arr[i].first; dp[0] = 0; int a, b, last, i = 1; while (arr[i].second == arr[i+1].second) i++; b = i; for (int j = 1; j <= i; j++) dp[j] = dp[j-1] + arr[b+1].first - arr[j].first; for (i++; i < arr.size(); i++) { if (arr[i].second != arr[i-1].second) { a = b; b = 0; last = arr[i-1].first; ll val = 0; for (int j = i-1; j >= i-a; j--) { val += arr[i].first - arr[j].first; dp[i] = min(dp[i], dp[j-1] + val); } } b++; if (b <= a) { dp[i] = min(dp[i], dp[i-1] + arr[i].first - last); dp[i] = min(dp[i], dp[i-2*b] + (sum[i] - sum[i-b]) - (sum[i-b] - sum[i-2*b])); } else { dp[i] = min(dp[i], dp[i-1] + arr[i].first - last); } } return dp[arr.size()-1]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 360 KB | Output is correct |
3 | Incorrect | 0 ms | 360 KB | 3rd lines differ - on the 1st token, expected: '15280', found: '15304' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 21 ms | 6492 KB | Output is correct |
4 | Correct | 23 ms | 6600 KB | Output is correct |
5 | Correct | 19 ms | 6604 KB | Output is correct |
6 | Correct | 25 ms | 8748 KB | Output is correct |
7 | Correct | 26 ms | 8620 KB | Output is correct |
8 | Correct | 25 ms | 8656 KB | Output is correct |
9 | Correct | 35 ms | 8756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 360 KB | Output is correct |
2 | Correct | 0 ms | 360 KB | Output is correct |
3 | Incorrect | 36 ms | 8656 KB | 3rd lines differ - on the 1st token, expected: '1068938599', found: '1078229293' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 360 KB | Output is correct |
2 | Incorrect | 30 ms | 8064 KB | 3rd lines differ - on the 1st token, expected: '373710605', found: '373748114' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 360 KB | Output is correct |
3 | Incorrect | 0 ms | 360 KB | 3rd lines differ - on the 1st token, expected: '15280', found: '15304' |
4 | Halted | 0 ms | 0 KB | - |