Submission #1047993

#TimeUsernameProblemLanguageResultExecution timeMemory
1047993TrentWiring (IOI17_wiring)C++17
17 / 100
1073 ms10136 KiB
#include "wiring.h" #include "bits/stdc++.h" using namespace std; #define forR(i, x) for(int i = 0; i < (x); ++i) #define REP(i, a, b) for(int i = (a); i < (b); ++i) #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vll; typedef vector<vll> vvll; const ll INF = 1e17; struct grp{ char ty; vi pos; }; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size(), m = b.size(); vector<grp> gps; int api=0, bpi=0; while(api < n || bpi < m) { if(api < n && (bpi == m || r[api] < b[bpi])) { gps.push_back({'r', {}}); while(api < n && (bpi == m || r[api] < b[bpi])) { gps.back().pos.push_back(r[api]); ++api; } } else { gps.push_back({'b', {}}); while(bpi < m && (api == n || r[api] > b[bpi])) { gps.back().pos.push_back(b[bpi]); ++bpi; } } } int l = gps.size(); vi cnt(l); forR(i, l) cnt[i] = gps[i].pos.size(); vvll dp(l); forR(i, l) dp[i].resize(cnt[i] + 1); forR(i, l) { if(i == 0) { forR(j, cnt[i]) dp[i][j] = INF; dp[i][cnt[i]] = 0; } else { ll sam = INF; multiset<ll> lav; vector<ll> aCh(cnt[i-1] + 1); forR(las, cnt[i-1] + 1) { ll cTot = dp[i-1][las]; REP(j, cnt[i-1] - las, cnt[i-1]) cTot += gps[i-1].pos.back() - gps[i-1].pos[j]; cTot += (ll) las * (gps[i].pos.front() - gps[i-1].pos.back()); lav.insert(cTot); aCh[las] = cTot; } ll bckTot = 0; forR(bck, cnt[i] + 1) { if(bck > 0) bckTot += gps[i].pos[bck-1] - gps[i].pos.front(); if(bck <= cnt[i-1]) { lav.erase(lav.find(aCh[bck])); sam = min(sam, aCh[bck] - (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back())); } int fwd = cnt[i] - bck; dp[i][fwd] = sam + bckTot + (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back()); if(!lav.empty()) { dp[i][fwd] = min(dp[i][fwd], *lav.begin() + bckTot); } } } } return dp[l-1][0]; }
#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...