# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1062823 | Zicrus | 전선 연결 (IOI17_wiring) | C++17 | 46 ms | 12208 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);
}
return solve(0, r.size()-1, n-1);
// Run dp
//dp = vector<ll>(n, 1ll << 62ll);
}
컴파일 시 표준 에러 (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... |