| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1072545 | ArthuroWich | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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];
}