이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define abs(x) ((x) > 0 ? (x) : (-(x)))
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pil;
const int MAX_N = 100005;
const LL inf = (1LL<<60);
LL sum_r[MAX_N], sum_b[MAX_N];
int idx[2 * MAX_N];
LL t[2 * MAX_N];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size();
int m = b.size();
for(int i=1;i<=n + m;i++) t[i] = inf;
for(int i=0;i<2 * MAX_N;i++) idx[i] = -1;
for(int i=1;i<=n;i++) sum_r[i] = sum_r[i - 1] + r[i - 1];
for(int i=1;i<=m;i++) sum_b[i] = sum_b[i - 1] + b[i - 1];
idx[MAX_N] = 0;
int sum_idx = MAX_N;
for(int i=0, j=0 ; i<n || j<m ; ){
if(j == m || r[i] < b[j]){
if(j != 0) t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(r[i] - b[j - 1]));
if(j < m) t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(r[i] - b[j]));
sum_idx++;
i++;
}else{
if(i != 0) t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(b[j] - r[i - 1]));
if(i < n) t[i + j + 1] = min(t[i + j + 1], t[i + j] + abs(b[j] - r[i]));
sum_idx--;
j++;
}
if(idx[sum_idx] == -1){
idx[sum_idx] = i + j;
continue;
}
int l = ((i + j) - idx[sum_idx]) / 2;
t[i + j] = min(t[i + j], t[idx[sum_idx]] + abs((sum_r[i] - sum_r[i - l]) - (sum_b[j] - sum_b[j - l])));
idx[sum_idx] = i + j;
}
return t[n + m];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |