# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1197627 | MateiKing80 | Wiring (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
using ll = long long;
#defint int ll
const int INF = 1e18;
int min_total_length(vector<signed> R, vector<signed> B) {
int N, M;
N = R.size();
M = B.size();
vector<pair<int, int>> P;
for (auto &i : R)
P.emplace_back(i, 1);
for (auto &i : B)
P.emplace_back(i, -1);
sort(P.begin(), P.end());
reverse(R.begin(), R.end());
reverse(B.begin(), B.end());
int x = M;
int r = -INF, b = -INF, D = 0, S = 0;
vector<pair<int, int>> lst(N + M + 1, {INF, INF});
lst[M] = {0, 0};
for (auto &i : P) {
int E = 0;
(i.sc == 1 ? R : B).pop_back();
x += i.sc;
S += i.fr * i.sc;
if (i.sc == 1) {
r = i.fr;
E = D+i.fr-b;
if (B.size())
E = min(E, D + B.back() - i.fr);
}
if (i.sc == -1) {
b = i.fr;
E = D+i.fr-r;
if (R.size())
E = min(E, D + R.back() - i.fr);
}
D = min(E, lst[x].fr + abs(lst[x].sc - S));
lst[x] = {D, S};
}
return D;
}