| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1194461 | mannshah1211 | 전선 연결 (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18;
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
vector<pair<long long, int>> all;
all.emplace_back(-1, 0);
for (int i = 0; i < n; i++) {
all.emplace_back(r[i], 0);
}
for (int i = 0; i < m; i++) {
all.emplace_back(b[i], 1);
}
sort(all.begin(), all.end());
vector<long long> dp(all.size() + 1, inf);
auto Cost = [&](vector<long long> big, vector<long long> small) {
// big is the one that comes later; small is the one that comes earlier
if (big.size() == small.size()) {
return accumulate(big.begin(), big.end(), int64_t(0)) - accumulate(small.begin(), small.end(), int64_t(0));
} else if (big.size() > small.size()) {
return accumulate(big.begin(), big.end(), int64_t(0)) - accumulate(small.begin(), small.end(), int64_t(0)) - ((long long) (big.size() - small.size()) * ((long long) (small[0])));
} else {
return accumulate(big.begin(), big.end(), int64_t(0)) - accumulate(small.begin(), small.end(), int64_t(0)) + ((long long) (small.size() - big.size()) * ((long long) (big[0])));
}
};
vector<long long> cur;
int color = all[1].second;
dp[0] = 0;
for (int i = 1; i <= n + m; i++) {
if (color == all[i].second) {
cur.push_back(all[i].first);
} else {
cur.clear();
cur.push_back(all[i].first);
color = all[i].second;
}
bool found_opp = false;
vector<long long> opp;
for (int j = i - 1; j >= 1; j--) {
if (all[j].second != all[i].second) {
found_opp = true;
opp.push_back(all[j].first);
dp[i] = min(dp[i], dp[j - 1] + Cost(cur, opp));
} else if (all[j].second == all[i].second) {
if (found_opp) {
break;
}
}
}
}
return dp[n + m];
}