#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int min_total_length(vector<int32_t> a, vector<int32_t> b) {
if (a.size() > b.size()) swap(a, b);
int n = a.size(), m = b.size();
vector<pair<int,int>> vec = {{-INF, 0}};
for (int i:a) vec.push_back({i, -1});
for (int i:b) vec.push_back({i, 1});
sort(vec.begin(), vec.end());
int sz = n+m;
int pa[sz+1], pb[sz+1], sa[sz+2], sb[sz+2];
pa[0] = pb[0] = -INF;
for (int i=1;i<=sz;i++) {
pa[i] = pa[i-1], pb[i] = pb[i-1];
if (vec[i].second == -1) pa[i] = vec[i].first;
else pb[i] = vec[i].first;
}
sa[sz+1] = sb[sz+1] = INF;
for (int i=sz;i>=1;i--) {
sa[i] = sa[i+1], sb[i] = sb[i+1];
if (vec[i].second == -1) sa[i] = vec[i].first;
else sb[i] = vec[i].first;
}
pair<int,int> dp[sz];
for (int i=0;i<sz;i++) dp[i] = {INF, -INF};
dp[0 + n] = {0, 0};
int last = 0, val = 0, sum = 0, pos = 1;
for (auto [i, del]:vec) if (del) {
val += del;
sum += i * del;
int cur;
if (del == -1) {
int adj = min(i - pb[pos], sb[pos] - i);
cur = min(last + adj, dp[val + n].first + abs(sum - dp[val + n].second));
} else if (del == 1) {
int adj = min(i - pa[pos], sa[pos] - i);
cur = min(last + adj, dp[val + n].first + abs(sum - dp[val + n].second));
}
dp[val + n] = {cur, sum};
last = cur;
pos++;
}
return last;
}
# | 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... |