# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1062880 | Zicrus | 전선 연결 (IOI17_wiring) | C++17 | 63 ms | 13256 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long ll;
vector<ll> dp;
ll getDp(ll i) {
if (i < 0) return 0;
return dp[i];
}
ll n;
vector<pair<ll, pair<ll, ll>>> pos; // pos, {type, id in type}
vector<ll> sumL, sumR;
ll totalDist;
ll solve(ll low, ll high, ll i) {
ll cntL = high - low + 1;
ll cntH = i - high;
ll cutoff = high;
if (cntL > cntH) cutoff++;
ll resL = sumR[low] - sumR[high+1] - (totalDist - pos[cutoff].first) * cntL;
ll resH = sumL[i] - sumL[high] - pos[cutoff].first * cntH;
return resL + resH;
}
ll min_total_length(vector<int> r, vector<int> b) {
// Initialize pos
pos.clear();
for (int i = 0; i < r.size(); i++) pos.push_back({r[i], {0, i}});
for (int i = 0; i < b.size(); i++) pos.push_back({b[i], {1, i}});
sort(pos.begin(), pos.end());
n = pos.size();
for (int i = n-1; i >= n; i--) pos[i].first -= pos[0].first;
totalDist = pos.back().first;
// Initialize sums
sumL = vector<ll>(n);
sumR = vector<ll>(n);
for (int i = 1; i < n; i++) {
sumL[i] = sumL[i-1] + pos[i].first;
}
for (int i = n-2; i >= 0; i--) {
sumR[i] = sumR[i+1] + (totalDist - pos[i].first);
}
// Run dp
dp = vector<ll>(n, 1ll << 62ll);
int i = 0;
while (pos[i].second.first == pos[0].second.first) i++;
vector<int> last(2, --i);
vector<int> best(2);
while (++i < n) {
int t = pos[i].second.first;
int o = 1-t;
int high = last[o];
last[t] = i;
int start = pos[i].second.first == pos[i-1].second.first ? best[t] : high+1;
for (int j = start; j >= 0 && (pos[j].second.first == o || (j > 0 && pos[j-1].second.first == o)); j--) {
ll val = solve(j, high, i) + getDp(j-1);
if (val <= dp[i]) {
dp[i] = val;
best[t] = j;
}
else if (j <= high) {
break;
}
}
}
return dp.back();
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |