#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
int n;
long long dp[N], pre[N];
pair <int, int> p[N];
long long min_total_length(vector <int> r, vector <int> b){
for (auto &i : r) p[++ n] = {i, 0};
for (auto &i : b) p[++ n] = {i, 1};
sort(p + 1, p + n + 1);
p[0] = {-inf, 1 - p[1].second};
for (int i = 1; i <= n; ++ i) pre[i] += p[i].first;
for (int last = 1, i = 1; i <= n; ++ i){
int j = i;
while (j < n && p[j].second == p[j + 1].second) ++ j;
for (int k = last; k < i; ++ k) dp[k] = min(dp[k], dp[k - 1] + p[i].first - p[k].first);
long long Min = dp[i - 1], sum = 0;
for (int k = i; k <= j; ++ k){
sum += p[k].first - p[i - 1].first;
int vc = i * i - k - 1;
if (vc >= last){
Min = min(Min, dp[vc - 1] + 1ll * p[i - 1].first * (i - vc) - pre[i - 1] + pre[vc - 1]);
}
dp[k] = Min + sum;
}
last = i;
i = j;
}
return dp[n];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2396 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-547564' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2396 KB |
3rd lines differ - on the 1st token, expected: '904', found: '-20821' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2396 KB |
3rd lines differ - on the 1st token, expected: '316', found: '-1352' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
3rd lines differ - on the 1st token, expected: '27', found: '-6839' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2396 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-547564' |
2 |
Halted |
0 ms |
0 KB |
- |