# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1062814 | Zicrus | Wiring (IOI17_wiring) | C++17 | 1 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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--) {
sumL[i] = sumL[i+1] + (totalDist - pos[i].first);
}
return solve(0, r.size()-1, n-1);
// Run dp
//dp = vector<ll>(n, 1ll << 62ll);
}
Compilation message (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... |