제출 #40224

#제출 시각아이디문제언어결과실행 시간메모리
40224jackyliuxx전선 연결 (IOI17_wiring)C++14
0 / 100
0 ms2028 KiB
//#define DEBUG #include "wiring.h" #include <bits/stdc++.h> using namespace std; #define INF 2147483647 #define RED true #define BLUE false typedef long long LL; struct P { bool color; LL pos; }; bool cmp(P a, P b) { return a.pos < b.pos; } vector<P> arr; vector<int> head; vector<LL> lsum, lcnt; vector<int> tail; vector<LL> rsum, rcnt; vector<LL> dp; LL dpv(int x) { if (x < 0) { return 0; } else { return dp[x]; } } LL calc(int l, int r) { #ifdef DEBUG cout << "calc " << l << ' ' << r << endl; cout << "rsum l: " << rsum[l] << endl; cout << "lsum r: " << lsum[r] << endl; cout << "rcnt l: " << rcnt[l] << endl; cout << "lcnt r: " << rcnt[r] << endl; cout << "tail l: " << tail[l] << endl; cout << "head r: " << head[r] << endl; #endif LL ret = min(dpv(l), dpv(l - 1)) + rsum[l] + lsum[r] + max(rcnt[l], lcnt[r]) * (arr[head[r]].pos - arr[tail[l]].pos); #ifdef DEBUG cout << "ret: " << ret << endl; #endif return ret; } long long min_total_length(std::vector<int> r, std::vector<int> b) { for (size_t i = 0; i < r.size(); i++) { arr.push_back({RED, r[i]}); } for (size_t i = 0; i < b.size(); i++) { arr.push_back({BLUE, b[i]}); } int n = arr.size(); head.assign(n, 0); lsum.assign(n, 0); lcnt.assign(n, 1); tail.assign(n, 0); rsum.assign(n, 0); rcnt.assign(n, 1); dp.assign(n, INF); sort(arr.begin(), arr.end(), cmp); head[0] = 0; for (int i = 1; i < n; i++) { if (arr[i].color != arr[i - 1].color) { head[i] = i; lsum[i] = 0; lcnt[i] = 1; } else { head[i] = head[i - 1]; lsum[i] = lsum[i - 1] + (arr[i].pos - arr[head[i]].pos); lcnt[i] = lcnt[i - 1] + 1; } } tail[n - 1] = n - 1; for (int i = n - 2; i >= 0; i--) { if (arr[i].color != arr[i + 1].color) { tail[i] = i; rsum[i] = 0; rcnt[i] = 1; } else { tail[i] = tail[i + 1]; rsum[i] = rsum[i + 1] + (arr[tail[i]].pos - arr[i].pos); rcnt[i] = rcnt[i + 1] + 1; } } int prehead = -1; int prepos = -1; for (int i = 1; i < n; i++) { if (arr[i].color != arr[i - 1].color) { prehead = head[i - 1]; prepos = i - 1; dp[i] = calc(prepos, i); while (prepos > prehead && calc(prepos - 1, i) <= dp[i]) { dp[i] = calc(prepos - 1, i); prepos--; } } else if (head[i] > 0) { dp[i] = calc(prepos, i); if (prepos > prehead && calc(prepos - 1, i) <= dp[i]) { dp[i] = calc(prepos - 1, i); prepos--; } } #ifdef DEBUG cout << i << " pos: " << arr[i].pos << " dp: " << dp[i] << " spos:" << prepos << endl; #endif } return dp[n - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...