제출 #434843

#제출 시각아이디문제언어결과실행 시간메모리
434843jli12345Palembang Bridges (APIO15_bridge)C++14
22 / 100
165 ms5584 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int K, N; pair<int, int> arr[200100]; ll sum = 0; bool comp(int a, int b){ return arr[a].first+arr[a].second < arr[b].first+arr[b].second; } priority_queue<int> pql; priority_queue<int, vector<int>, greater<int> > pqr; ll lsum, rsum; ll pref[200100], suff[200100]; void insert(int val){ if (pql.empty()){ pql.push(val); lsum += val; return; } if (val > pql.top()){ if ((int)pql.size() == (int)pqr.size()){ pqr.push(val); rsum += val; int ins = pqr.top(); pqr.pop(); rsum -= ins; pql.push(ins); lsum += ins; } else { pqr.push(val); rsum += val; } } else { if ((int)pql.size() == (int)pqr.size()){ pql.push(val); lsum += val; } else { pql.push(val); lsum += val; int ins = pql.top(); pql.pop(); lsum -= ins; pqr.push(ins); rsum += ins; } } } int main(){ cin >> K >> N; vector<int> v; for (int i = 1; i <= N; i++){ char ca, cb; int pa, pb; cin >> ca >> pa >> cb >> pb; if (ca == cb) sum += abs(pb-pa); else { v.push_back(i); arr[i] = make_pair(pa, pb); } } sort(v.begin(), v.end(), comp); /*for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " "; cout << "\n";*/ for (int i = 0; i < (int)v.size(); i++){ insert(arr[v[i]].first); insert(arr[v[i]].second); pref[i] = rsum-lsum+i+1; //cout << rsum << " " << lsum << " " << pref[i] << "\n"; } while (pql.empty()) pql.pop(); while (pqr.empty()) pqr.pop(); lsum = 0; rsum = 0; for (int i = (int)v.size()-1; i >= 0; i--){ insert(arr[v[i]].first); insert(arr[v[i]].second); suff[i] = rsum-lsum+(int)v.size()-i; //cout << rsum << " " << lsum << " " << suff[i] << "\n"; } ll add = min(pref[0],suff[(int)v.size()-1]); for (int i = 0; i < (int)v.size()-1; i++){ add = min(add, pref[i]+suff[i+1]); } if (K == 1){ cout << sum+pref[v.size()-1] << "\n"; } else { cout << sum+add << "\n"; } }
#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...