제출 #700860

#제출 시각아이디문제언어결과실행 시간메모리
700860Abrar_Al_SamitPalembang Bridges (APIO15_bridge)C++17
78 / 100
280 ms13552 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> const long long INF = 1e18; void PlayGround() { int k, n; cin>>k>>n; long long ans = 0; vector<pair<int,int>>bag; for(int i=0; i<n; ++i) { char p, q; int s, t; cin>>p>>s>>q>>t; if(s>t) swap(s, t); if(p==q) { ans += t - s; } else { bag.emplace_back(s, t); } } int m = bag.size(); ans += m; if(m==0) { cout<<ans<<'\n'; return; } sort(bag.begin(), bag.end(), [&] (pii x, pii y) { return x.first+x.second<y.first+y.second; }); long long pre[m]; long long S1 = 0, S2 = 0; multiset<int>m1, m2; for(int i=0; i<m; ++i) { m1.insert(bag[i].first), m2.insert(bag[i].second); S1 += bag[i].first; S2 += bag[i].second; while(*prev(m1.end())>*m2.begin()) { S1 -= *prev(m1.end()); S1 += *m2.begin(); S2 -= *m2.begin(); S2 += *prev(m1.end()); m2.insert(*prev(m1.end())); m1.erase(prev(m1.end())); m1.insert(*m2.begin()); m2.erase(m2.begin()); } int med = *m2.begin(); pre[i] = med * (i+1) - S1 + S2 - med * (i+1); } long long best = INF; S1 = S2 = 0; m1.clear(), m2.clear(); for(int i=m-1; i>=0; --i) { m1.insert(bag[i].first), m2.insert(bag[i].second); S1 += bag[i].first; S2 += bag[i].second; while(*prev(m1.end())>*m2.begin()) { S1 -= *prev(m1.end()); S1 += *m2.begin(); S2 -= *m2.begin(); S2 += *prev(m1.end()); m2.insert(*prev(m1.end())); m1.erase(prev(m1.end())); m1.insert(*m2.begin()); m2.erase(m2.begin()); } long long med = *m2.begin(); long long cur = med * (m-i) - S1 + S2 - med * (m-i); if(i) cur += pre[i-1]; best = min(best, cur); } ans += best; cout<<ans<<'\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); PlayGround(); return 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...