| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125303 |
2019-07-05T05:09:34 Z |
turbat |
Wiring (IOI17_wiring) |
C++14 |
|
2 ms |
420 KB |
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
long long dp[200005], sum[200005];
pair <int , int> p[100005];
int n, m;
long long cost(int l, int r, int to){
if (r - l + 1 < to - r)
return sum[to] - 2 * sum[r] + sum[l - 1] + (to - r - r + l - 1) * p[r].first;
return sum[to] - 2 * sum[r] + sum[l - 1] + (r - l + 1 - to + r) * p[r + 1].first;
}
void solve (int l, int r){
if (r == n + m) return;
int curl = r, curr = r + 1;
while (curr <= n + m){
while (curl > l && dp[curl - 1] + cost(curl, r, curr) > dp[curl - 2] + cost(curl, r, curr))
curl--;
dp[curr] = dp[curl - 1] + cost(curl, r, curr);
if (p[curr].second != p[curr + 1].second){
solve(r + 1, curr);
break;
}
curr++;
}
}
long long min_total_length(vector<int> r, vector<int> b) {
int l = 0, l1 = 0;
n = r.size(), m = b.size();
p[n + m + 1].second = 2;
r.push_back(2e9);
b.push_back(2e9);
for (int i = 1;i <= n + m;i++){
sum[i] = sum[i - 1];
sum[i] += min(r[l], b[l1]);
p[i].first = min(r[l], b[l1]);
if (r[l] > b[l1]){
p[i].second = 1;
l1++;
}
else l++;
}
int bg, ed;
for (int i = 2;i <= n + m;i++)
if (p[i].second == p[i - 1].second){
bg = i - 1;
break;
}
for (int i = bg + 1;i <= n + m;i++){
dp[i] = cost(1, bg, i);
if (p[i].second != p[i + 1].second){
solve(bg + 1, i);
break;
}
}
return dp[n + m];
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:46:10: warning: unused variable 'ed' [-Wunused-variable]
int bg, ed;
^~
wiring.cpp:46:6: warning: 'bg' may be used uninitialized in this function [-Wmaybe-uninitialized]
int bg, ed;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
420 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '22620' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '904', found: '849' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '316', found: '360' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '27', found: '29' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
420 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '22620' |
| 2 |
Halted |
0 ms |
0 KB |
- |
