이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size(), cr = 0, cb = 0;
vector<pair<int, int>> a = {{0,0}};
for (auto x : r)
a.emplace_back(x, 0);
for (auto x : b)
a.emplace_back(x, 1);
sort(a.begin() + 1, a.end());
vector<ll> dp(n + m + 1, 1e18), sr(n + m + 1), sb(n + m + 1);
vector<int> last(n + m + 1, -1);
dp[0] = 0;
last[m] = 0;
for (int i = 1; i <= n + m; ++i) {
auto [x, t] = a[i];
++(t ? cb : cr);
sr[i] = sr[i - 1], sb[i] = sb[i - 1];
(t ? sb[i] : sr[i]) += x;
if (t) {
int j = lower_bound(r.begin(), r.end(), x) - r.begin();
if (j != n)
dp[i] = min(dp[i], dp[i - 1] + r[j] - x);
if (j)
dp[i] = min(dp[i], dp[i - 1] + x - r[j - 1]);
}
else {
int j = lower_bound(b.begin(), b.end(), x) - b.begin();
if (j != m)
dp[i] = min(dp[i], dp[i - 1] + b[j] - x);
if (j)
dp[i] = min(dp[i], dp[i - 1] + x - b[j - 1]);
}
if (last[cr - cb + m] != -1) {
int l = last[cr - cb + m];
dp[i] = min(dp[i], dp[l] + abs((sr[i] - sr[l]) - (sb[i] - sb[l])));
}
last[cr - cb + m] = i;
}
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... |