| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 422297 | timmyfeng | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const long long L = 1000000000000000LL;
long long min_total_length(vector<int> r, vector<int> b) {
vector<array<int, 2>> points;
for (auto i : r) {
points.push_back({i, 0});
}
for (auto i : b) {
points.push_back({i, 1});
}
sort(points.begin(), points.end());
vector<long long> cost;
for (int i = 0, j = 0; i < (int) points.size(); i = j) {
while (j < (int) points.size() && points[j][1] == points[i][1]) {
++j;
}
if (i == 0) {
cost.resize(j + 1);
for (int k = 0; k < j; ++k) {
cost[j] += points[j - 1][0] - points[k][0];
cost[k] = L;
}
} else {
long long gap = points[i][0] - points[i - 1][0];
vector<long long> prefix = cost;
for (int k = 1; k < (int) cost.size(); ++k) {
prefix[k] = min(prefix[k], prefix[k - 1]);
}
vector<long long> suffix = cost;
for (int k = cost.size() - 2; k >= 0; --k) {
suffix[k] = min(suffix[k] + k * gap, suffix[k + 1]);
}
long long sum = 0;
cost.resize(j - i + 1);
for (int k = 0; k <= j - i; ++k) {
sum += k > 0 ? points[i + k - 1][0] - points[i][0] : 0;
if (k < (int) prefix.size()) {
cost[k] = sum + min(suffix[k], prefix[k] + k * gap);
} else {
cost[k] = sum + prefix.back() + k * gap;
}
}
sum = 0;
for (int k = j - i - 1; k >= 0; --k) {
sum += points[j - 1][0] - points[i + k][0];
cost[k] += sum;
}
reverse(cost.begin(), cost.end());
}
}
return cost[0];
}
int main() {
int n, m;
cin >> n >> m;
vector<int> r(n), b(m);
for (auto &i : r) {
cin >> i;
}
for (auto &i : b) {
cin >> i;
}
cout << min_total_length(r, b) << "\n";
}