Submission #1047990

#TimeUsernameProblemLanguageResultExecution timeMemory
1047990TrentWiring (IOI17_wiring)C++17
17 / 100
1096 ms10044 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 { forR(bck, cnt[i] + 1) { int fwd = cnt[i] - bck; dp[i][fwd] = INF; 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]; forR(j, bck) cTot += gps[i].pos[j] - gps[i].pos.front(); cTot += (ll) max(las, bck) * (gps[i].pos.front() - gps[i-1].pos.back()); dp[i][fwd] = min(dp[i][fwd], cTot); } } } } 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...