제출 #407377

#제출 시각아이디문제언어결과실행 시간메모리
407377Peti전선 연결 (IOI17_wiring)C++14
0 / 100
57 ms8428 KiB
#include <bits/stdc++.h> #include "wiring.h" using namespace std; long long INF = (long long)1e17; vector<pair<int, int>> v; vector<long long> ossz; long long ertek(int l, int m, int r){ long long ossz1 = ossz[m-1]-ossz[l-1], ossz2 = ossz[r]-ossz[m-1]; if(m-l < r-m+1) ossz1 += (long long)v[m-1].first*(r-2*m+l+1); else ossz2 += (long long)v[m].first*(2*m-r-l-1); return ossz2 - ossz1; } long long min_total_length(std::vector<int> r, std::vector<int> b) { v.resize(r.size()+b.size()+1); int n = 0; for(int x : r) v[n++] = make_pair(x, 0); for(int x : b) v[n++] = make_pair(x, 1); if(r[0] < b[0]) v[n++] = make_pair(-1, 0); else v[n++] = make_pair(-1, 1); sort(v.begin(), v.end()); ossz.resize(n); ossz[0] = v[0].first; for(int i = 1; i < n; i++) ossz[i] = ossz[i-1] + (long long)v[i].first; vector<long long> dp(n, INF); dp[0] = 0ll; for(int i = 1; i < n && v[i].second == v[0].second; i++) dp[i] = (long long)i*INF; int lastr = -1, lastb = -1, j = -1; for(int i = 1; i < n; i++){ if(v[i].second == 0 && (lastr == -1 || v[i-1].second != 0)){ lastr = i; j = lastr-1; }else if(v[i].second == 1 && (lastb == -1 || v[i-1].second != 1)){ lastb = i; j = lastb-1; } if(lastr == -1 || lastb == -1) continue; while(j > min(lastb, lastr) && ertek(j, max(lastb, lastr), i)+dp[j-1] > ertek(j-1, max(lastb, lastr), i)+dp[j-2]) j--; dp[i] = ertek(j, max(lastb, lastr), i)+dp[j-1]; } 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...