제출 #1196405

#제출 시각아이디문제언어결과실행 시간메모리
1196405Aviansh전선 연결 (IOI17_wiring)C++20
100 / 100
27 ms5416 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long min_total_length(vector<int> r, vector<int> b) { int n = r.size(); int m = b.size(); vector<pair<int,bool>>both(n+m);// red is true int i = 0; int j = 0; int prevr = -1e9; int prevb = -1e9; int closest[n+m]; while(i<n||j<m){ if(i<n&&j<m){ if(r[i]<b[j]){ both[i+j].first=r[i]; both[i+j].second=true; prevr = r[i]; closest[i+j]=r[i]-prevb; i++; } else{ both[i+j].first=b[j]; prevb=b[j]; closest[i+j]=b[j]-prevr; both[i+j].second=false; j++; } } else if(i<n){ both[i+j].first=r[i]; both[i+j].second=true; prevr = r[i]; closest[i+j]=r[i]-prevb; i++; } else{ both[i+j].first=b[j]; prevb=b[j]; closest[i+j]=b[j]-prevr; both[i+j].second=false; j++; } } prevr = 2e9; prevb = 2e9; for(int i = n+m-1;i>=0;i--){ if(both[i].second){ //is red closest[i]=min(closest[i],prevb-both[i].first); prevr = both[i].first; } else { //is blue closest[i]=min(closest[i],prevr-both[i].first); prevb = both[i].first; } } //closest done long long ans = 0; priority_queue<int,vector<int>,greater<int>>pqr,pqb; for(int i = 0;i<n+m;i++){ if(both[i].second){ //red if(pqb.size()==0||closest[i]<both[i].first+pqb.top()){ ans+=closest[i]; pqr.push(-closest[i]-both[i].first); } else{ int a = pqb.top(); pqb.pop(); ans+=both[i].first+a; pqr.push({-both[i].first-a-both[i].first}); } } else{ //blue if(pqr.size()==0||closest[i]<both[i].first+pqr.top()){ ans+=closest[i]; pqb.push(-closest[i]-both[i].first); } else{ int a = pqr.top(); pqr.pop(); ans+=both[i].first+a; pqb.push({-both[i].first-a-both[i].first}); } } } return ans; }
#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...