# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
940913 | 2024-03-08T02:08:53 Z | beaboss | Wiring (IOI17_wiring) | C++14 | 33 ms | 10820 KB |
// Source: https://oj.uz/problem/view/IOI17_wiring // #include "wiring.h" #include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<ll, ll> pii; typedef vector<pii> vpii; typedef vector<ll> vi; #define FOR(i, a, b) for (ll i = (a); i<b; i++) bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; } bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; } const ll INF = 1e9; ll min_total_length(vector<int> r, vector<int> b) { vector<vi> dp; vector<vi> pref; ll n = r.size(), m = b.size(); ll i, j; i = j = 0; r.pb(INF); b.pb(INF); while (i != n || j != m) { ll sz = 0; ll here=pref.size(); pref.pb({0}); if (r[i] < b[j]) { while (i != n && r[i] < b[j]) { pref[here].pb(r[i]); sz++;i++; } } else { while (j != m && b[j] < r[i]) { pref[here].pb(b[j]); sz++;j++; } } dp.pb(vi(sz+1, INF)); assert(pref[here].size() == sz+1); FOR(i, 1, sz+1) pref[here][i] += pref[here][i-1]; } dp[0][0] = 0; FOR(i, 1, dp.size()) { ll best = INF; FOR(j, 0, dp[i].size()) { if ((ll) dp[i-1].size() - j - 1 >= 0) { // cout << 'd' << endl; // cout << best << endl; best = min(best, dp[i-1][dp[i-1].size() - j-1] - (pref[i-1][dp[i-1].size()-1] - pref[i-1][dp[i-1].size() - j-1])); // cout << best << endl; // cout << dp[i-1].size() - j-1 << endl; } // cout << i << j << ' ' << best << pref[i][j] << endl; ckmin(dp[i][j], best + pref[i][j]); best -= pref[i-1][pref[i-1].size() - 1] - pref[i-1][pref[i-1].size() - 2]; // get the last element from before // cout << ' ' << dp[i][j] << endl; } best = INF; for (ll j = dp[i-1].size() - 1; j >= 0; j--) { best = min(best, dp[i-1][dp[i-1].size() - j - 1] - (pref[i-1][dp[i-1].size()-1] - pref[i-1][dp[i-1].size() - j - 1])); // cout << best << endl; if (j < dp[i].size()) ckmin(dp[i][j], best + pref[i][j]); best += pref[i][1]; // cout << i << j << ' ' << dp[i][j] << endl; } } return dp[dp.size()-1][dp[dp.size()-1].size()-1]; } // int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // ll res = min_total_length({0, 1, 2, 3}, {5, 6}); // cout << res << endl; // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 432 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 432 KB | Output is correct |
10 | Correct | 0 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 600 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 16 ms | 5388 KB | 3rd lines differ - on the 1st token, expected: '41596985758595', found: '1000000000' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 33 ms | 10820 KB | 3rd lines differ - on the 1st token, expected: '1068938599', found: '1000000000' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 18 ms | 5344 KB | Output is correct |
3 | Correct | 22 ms | 9036 KB | Output is correct |
4 | Correct | 19 ms | 6988 KB | Output is correct |
5 | Correct | 24 ms | 9020 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 440 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Incorrect | 23 ms | 6440 KB | 3rd lines differ - on the 1st token, expected: '2300170053', found: '1000000000' |
19 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 432 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 432 KB | Output is correct |
10 | Correct | 0 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 600 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Incorrect | 16 ms | 5388 KB | 3rd lines differ - on the 1st token, expected: '41596985758595', found: '1000000000' |
20 | Halted | 0 ms | 0 KB | - |