이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LINF = (ll) 1e18;
long long min_total_length(std::vector<int> a, std::vector<int> b) {
int n = (int) a.size(), m = (int) b.size();
vector< pair<int, int> > v;
for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
sort(v.begin(), v.end());
v.insert(v.begin(), {0, -1});
vector<int> seg(n + m + 1); seg[1] = 0; seg[0] = -5;
vector<int> sz;
int len = 1;
for (int i = 2; i <= n + m; i++) {
seg[i] = seg[i - 1];
len++;
if (v[i].second != v[i - 1].second) {
sz.push_back(len - 1);
seg[i]++, len = 1;
}
}
sz.push_back(len);
vector<ll> dp(n + m + 1, LINF); dp[0] = 0;
for (int i = 1; i <= n + m; i++) {
if (seg[i] == 0) continue;
int cnt_l = 0, cnt_r = 0;
ll sum_l = 0, sum_r = 0;
int last_l = 0, last_r = -1;
for (int j = i - 1; j >= 0; j--) {
if (seg[j + 1] == seg[i]) {
cnt_l++; sum_l += v[j + 1].first;
last_l = v[j + 1].first;
}
if (seg[j + 1] == seg[i] - 1) {
cnt_r++; sum_r += v[j + 1].first;
if (last_r == -1) last_r = v[j + 1].first;
}
if (cnt_r > 0) {
ll add = sum_l - sum_r;
if (cnt_l > cnt_r) add -= last_r * (cnt_l - cnt_r);
else add += last_l * (cnt_r - cnt_l);
dp[i] = min(dp[i], dp[j + 1] + add);
dp[i] = min(dp[i], dp[j] + add);
}
if (seg[j] < seg[i] - 1) break;
}
}
return dp[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... |