# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
826458 | 2023-08-15T15:26:47 Z | caganyanmaz | Wiring (IOI17_wiring) | C++17 | 23 ms | 4976 KB |
#include <bits/stdc++.h> //#define DEBUGGING #define pb push_back #define int int64_t using namespace std; #include "wiring.h" #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif constexpr static int MXN = 1e5; #ifdef DEBUGGING constexpr static int MXG = 9; #else constexpr static int MXG = 205; #endif constexpr static int INF = 1e10; deque<int> r, b; long long subtask2() { int m = r.back(); int sum = 0; for (int i : r) sum += m - i; for (int i : b) sum += i - m; if (r.size() > b.size()) sum += (b[0] - m) * (r.size() - b.size()); return sum; } vector<int> dp(MXG); vector<int> dp2(MXG); long long min_total_length(vector<int32_t> rr, vector<int32_t> bb) { for (int i : rr) r.push_back(i); for (int i : bb) b.push_back(i); if (r.back() < b[0]) return subtask2(); int g = 200; if (rr.size() > 200 || bb.size() > 200) g = 9; int current = 0; fill(dp.begin(), dp.begin() + g, INF); dp[0] = 0; if (r[0] > b[0]) swap(r, b); int mnr = -INF; debug(dp); while (r.size() || b.size()) { debug(r, b); vector<int> v; assert(v.size() < g); while (r.size() && (b.empty() || r[0] < b[0])) { v.pb(r[0]); r.pop_front(); } fill(dp2.begin(), dp2.begin() + g, INF); int rb = b[0], lb = v[0]; for (int i = 0; i <= v.size(); i++) // How many we're putting to right { int lsum = 0; int rsum = 0; for (int j = 0; j < v.size()-i; j++) lsum += v[j] - lb; for (int j = v.size()-i; j < v.size(); j++) rsum += rb - v[i]; debug(lsum, rsum); for (int j = 0; j < g; j++) // How many is coming from right { if (j < v.size()-i) // We need to take more dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum); else dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum); // We might need to give more as well (but it has 0 contribution so it doesn't matter) } } for (int i = 0; i < g; i++) dp[i] = dp2[i]; debug(dp); mnr = v.back(); swap(r, b); } return dp[0]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 296 KB | 3rd lines differ - on the 1st token, expected: '25859', found: '26657' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 304 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 14 ms | 3748 KB | Output is correct |
4 | Correct | 13 ms | 3900 KB | Output is correct |
5 | Correct | 14 ms | 3980 KB | Output is correct |
6 | Correct | 19 ms | 4748 KB | Output is correct |
7 | Correct | 23 ms | 4976 KB | Output is correct |
8 | Correct | 21 ms | 4624 KB | Output is correct |
9 | Correct | 18 ms | 4792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Incorrect | 0 ms | 212 KB | 3rd lines differ - on the 1st token, expected: '17703', found: '17575' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | 3rd lines differ - on the 1st token, expected: '27', found: '31' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 296 KB | 3rd lines differ - on the 1st token, expected: '25859', found: '26657' |
2 | Halted | 0 ms | 0 KB | - |