| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072545 | ArthuroWich | Wiring (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
int calc(vector<int> &r, vector<int> &b) {
int ans = 0, rbe, bbe;
rbe = r.front();
bbe = b.front();
for (int i = 0; i < min((int) r.size(), (int) b.size()); i++) {
ans += b[i]-r[i];
}
if (r.size() < b.size()) {
for (int i = r.size(); i < b.size(); i++) {
ans += b[i]-rbe;
}
} else {
for (int i = b.size(); i < r.size(); i++) {
ans += bbe-r[i];
}
}
return ans;
}
int min_total_length(vector<int32_t> r, vector<int32_t> b) {
int n = r.size()+b.size();
vector<pair<int, int>> a;
for (int i = 0; i < r.size(); i++) {
a.push_back({r[i], 0});
}
for (int i = 0; i < b.size(); i++) {
a.push_back({b[i], 1});
}
vector<int> dp(n, INT64_MAX);
sort(a.begin(), a.end());
for (int i = 1; i < n; i++) {
int l = -1, r = i;
vector<int> lv, rv;
for (int j = i; j >= 0; j--) {
if (a[j].second != a[r].second) {
l = j;
break;
} else {
rv.push_back(a[j].first);
}
}
if (l == -1) {
continue;
}
reverse(rv.begin(), rv.end());
if (dp[i-1] != INT64_MAX) {
dp[i] = min(dp[i], dp[i-1]+abs(a[r].first-a[l].first));
}
for (int j = l; j >= 0; j--) {
if (a[j].second == a[l].second) {
lv.push_back(a[j].first);
if (j-1 >= 0) {
if (dp[j-1] == INT64_MAX) {
continue;
}
dp[i] = min(dp[i], dp[j-1]+calc(lv, rv));
} else if (j == 0) {
dp[i] = min(dp[i], calc(lv, rv));
}
} else {
break;
}
}
}
return dp[n-1];
}