# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
43199 | 2018-03-10T14:33:22 Z | szawinis | Wiring (IOI17_wiring) | C++14 | 65 ms | 8928 KB |
#include "wiring.h" #include <bits/stdc++.h> #define pos first #define col second using namespace std; using ll = long long; const int N = 1e5+1; const ll INF = 1e17; int n; vector<pair<int,int> > a; ll s[N], dp[N]; ll min_total_length(std::vector<int> r, std::vector<int> b) { n = r.size() + b.size(); for(int i = 0; i < r.size(); i++) a.emplace_back(r[i], 0); for(int i = 0; i < b.size(); i++) a.emplace_back(b[i], 1); a.emplace_back(INT_MIN, INT_MIN); sort(a.begin(), a.end()); for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i].pos; fill(dp+1, dp+n+1, INF); for(int i = 2; i <= n; i++) { // case segments completely disjoint int k = i-1; while(k >= 0 && a[k].col == a[i].col) --k; if(!k) continue; for(int j = k-1; j >= 0 && a[j+1].col == a[k].col; j--) { ll res = dp[j] + (s[i] - s[k]) - (s[k] - s[j]); if(i-k > k-j) res -= 1ll * ((i-k) - (k-j)) * a[k].pos; else if(i-k < k-j) res += 1ll * ((k-j) - (i-k)) * a[k+1].pos; dp[i] = min(res, dp[i]); } // case segments intersect at one node if(k-1 >= 1 && a[k-1].col == a[i].col) dp[i] = min(dp[k] + s[i] - s[k] - 1ll * (i-k) * a[k].pos, dp[i]); } return dp[n]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 248 KB | Output is correct |
2 | Correct | 1 ms | 352 KB | Output is correct |
3 | Correct | 2 ms | 424 KB | Output is correct |
4 | Correct | 1 ms | 424 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 2 ms | 616 KB | Output is correct |
8 | Correct | 2 ms | 616 KB | Output is correct |
9 | Correct | 2 ms | 616 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
11 | Correct | 2 ms | 640 KB | Output is correct |
12 | Correct | 1 ms | 640 KB | Output is correct |
13 | Correct | 1 ms | 640 KB | Output is correct |
14 | Correct | 2 ms | 640 KB | Output is correct |
15 | Correct | 2 ms | 648 KB | Output is correct |
16 | Correct | 2 ms | 648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 648 KB | Output is correct |
2 | Correct | 2 ms | 648 KB | Output is correct |
3 | Runtime error | 48 ms | 7172 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 7172 KB | Output is correct |
2 | Correct | 1 ms | 7172 KB | Output is correct |
3 | Runtime error | 65 ms | 8816 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8816 KB | Output is correct |
2 | Runtime error | 49 ms | 8928 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 248 KB | Output is correct |
2 | Correct | 1 ms | 352 KB | Output is correct |
3 | Correct | 2 ms | 424 KB | Output is correct |
4 | Correct | 1 ms | 424 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 2 ms | 616 KB | Output is correct |
8 | Correct | 2 ms | 616 KB | Output is correct |
9 | Correct | 2 ms | 616 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
11 | Correct | 2 ms | 640 KB | Output is correct |
12 | Correct | 1 ms | 640 KB | Output is correct |
13 | Correct | 1 ms | 640 KB | Output is correct |
14 | Correct | 2 ms | 640 KB | Output is correct |
15 | Correct | 2 ms | 648 KB | Output is correct |
16 | Correct | 2 ms | 648 KB | Output is correct |
17 | Correct | 1 ms | 648 KB | Output is correct |
18 | Correct | 2 ms | 648 KB | Output is correct |
19 | Runtime error | 48 ms | 7172 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
20 | Halted | 0 ms | 0 KB | - |