제출 #1249502

#제출 시각아이디문제언어결과실행 시간메모리
1249502nikdWiring (IOI17_wiring)C++20
0 / 100
22 ms7616 KiB
#include "wiring.h" #include <bits/stdc++.h> #include <climits> #include <queue> using namespace std; using ll = long long; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size()+b.size(); //vector<ll> dp(n, -1); vector<pair<int, bool>> vec(n); int ii = 0; for(int j = 0; ii+j<n; ){ if(ii==r.size()){ vec[ii+j] = {b[j], 1}; j++; } else if(j == b.size()){ vec[ii+j] = {r[ii], 0}; ii++; } else if(b[j] < r[ii]){ vec[ii+j] = {b[j], 1}; j++; } else{ vec[ii+j] = {r[ii], 0}; ii++; } } vector<vector<int>> seq; vector<vector<ll>> dp; for(int i = 0; i<n; i++){ seq.push_back({vec[i].first}); dp.push_back({}); while(i+1<n && vec[i].second == vec[i+1].second){ seq.back().push_back(vec[i+1].first); i++; } dp.back().resize(seq.back().size()+1, -1); } dp[0][0] = 0; for(int i: seq[0]) dp[0][0] += seq[0].back()-i; for(int i = 1; i<seq.size()-1; i++){ dp[i][0] = dp[i-1].back(); ll delta = seq[i][0]-seq[i-1].back(); deque<array<ll, 2>> q; auto c = [&](array<ll, 2> arr, ll idx){ return arr[0]+max(arr[1], idx)*delta; }; for(int j = seq[i-1].size()-1; j>=0; j--){ if(dp[i-1][j] == -1) continue; array<ll, 2> nw = {dp[i-1][j], (ll)seq[i-1].size()-j}; ll cost = c(nw, 1); while(q.size() && cost <= c(q.back(), 1)) q.pop_back(); q.push_back(nw); } ll sm = 0; for(int j = 1; j<dp[i].size(); j++){ while(q.size() > 1 && c(q[0], j) >= c(q[1], j)) q.pop_front(); sm += seq[i][j-1]-seq[i][0]; dp[i][j] = c(q[0], j)+sm; } sm = 0; for(int j =dp[i].size()-2; j>=0; j--){ if(dp[i][j] != -1) dp[i][j] += sm; if(j> 0) sm += seq[i].back()-seq[i][j-1]; } int cc; } ll sol = LONG_LONG_MAX; int szl = seq.back().size(); int last = dp.size()-2; ll delta = seq.back()[0]-seq[last].back(); auto c2 = [&](array<ll, 2> arr, ll idx){ return arr[0]+max(arr[1], idx)*delta; }; for(int i = 0; i<dp[last].size()-1; i++){ sol = min(sol, c2({dp[last][i], (ll)seq[last].size()-i}, szl)); } for(int i = seq.back().size()-1; i>0; i--){ sol += seq.back()[i]-seq.back()[0]; } return sol; }
#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...