#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> s, vector<int> t) {
int n = s.size(), m = t.size(), si = 0, ti = 0;
vector<long long> ss(n+m+1), st(n+m+1), dp(n+m+1), c(2*n+2*m+2);
vector<pair<long long, int>> v;
v.push_back({-1, 0});
for (int i = 0; i < n; i++) {
v.push_back({s[i], 0});
}
for (int i = 0; i < m; i++) {
v.push_back({t[i], 1});
}
sort(v.begin(), v.end());
int x = n+m;
for (int i = 1; i <= n+m; i++) {
si = lower_bound(s.begin(), s.end(), v[i].first) - s.begin();
if(si == (int)s.size()) si--;
if(si > 0 && s[si] > v[i].first) si--;
ti = lower_bound(t.begin(), t.end(), v[i].first) - t.begin();
if(ti == (int)t.size()) ti--;
if(ti > 0 && t[ti] > v[i].first) ti--;
ss[i] = ss[i-1];
st[i] = st[i-1];
long long tmp = 0;
if(v[i].second == 1){
if(si < n-1) {
tmp = min(abs(s[si] - v[i].first), abs(s[si+1] - v[i].first));
} else {
tmp = abs(s[si] - v[i].first);
}
x++;
ss[i] += v[i].first;
} else {
if(ti < m-1) {
tmp = min(abs(t[ti] - v[i].first), abs(t[ti+1] - v[i].first));
} else {
tmp = abs(t[ti] - v[i].first);
}
x--;
st[i] += v[i].first;
}
if(c[x] != 0){
dp[i] = min(dp[i-1] + tmp, dp[c[x]] + abs(ss[i] - ss[c[x]] + st[c[x]] - st[i]));
} else {
dp[i] = dp[i-1] + tmp;
}
c[x] = i;
}
return dp[n+m];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '25965' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
30 ms |
14828 KB |
Output is correct |
4 |
Correct |
29 ms |
13768 KB |
Output is correct |
5 |
Incorrect |
29 ms |
13252 KB |
3rd lines differ - on the 1st token, expected: '41752125325332', found: '41752125344522' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '316', found: '324' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
44 ms |
17192 KB |
Output is correct |
3 |
Incorrect |
46 ms |
15396 KB |
3rd lines differ - on the 1st token, expected: '1116068', found: '1116069' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '25965' |
2 |
Halted |
0 ms |
0 KB |
- |