#include "wiring.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int sz = 2e5 + 10;
const ll inf = 1e18 + 18;
ll dp[sz][2];
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
int i = 0, j = 0, k = 0;
map<int,int> ma, mb;
while (i < n and j < m) {
if (r[i] < b[j]) {
ma[i] = k;
if (0 < j) {
int l = mb[j - 1];
dp[k][0] = dp[l][1] + r[i] - b[j - 1] + min(dp[k - 1][0], dp[k - 1][1]) - min(dp[l][0], dp[l][1]);
} else dp[k][0] = inf;
if (j < m) {
if (0 < k) dp[k][1] = min(dp[k - 1][0], dp[k - 1][1]);
dp[k][1] += b[j] - r[i];
} else dp[k][1] = inf;
i ++;
} else {
mb[j] = k;
if (0 < j) {
int l = ma[i - 1];
dp[k][0] = dp[l][1] + b[j] - r[i - 1] + min(dp[k - 1][0], dp[k - 1][1]) - min(dp[l][0], dp[l][1]);
} else dp[k][0] = inf;
if (j < m) {
if (0 < k) dp[k][1] = min(dp[k - 1][0], dp[k - 1][1]);
dp[k][1] += r[i] - b[j];
} else dp[k][1] = inf;
j ++;
}
k ++;
}
return min(dp[k - 1][0], dp[k - 1][1]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '30890' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '904', found: '623' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '316', found: '176' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '27', found: '36' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '30890' |
2 |
Halted |
0 ms |
0 KB |
- |