Submission #1281375

#TimeUsernameProblemLanguageResultExecution timeMemory
1281375Faisal_SaqibPalembang Bridges (APIO15_bridge)C++17
100 / 100
82 ms8808 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back priority_queue<ll> lt; // we will need to pop the maximum priority_queue<ll,vector<ll>,greater<ll>> rt; ll med=-1,lsm=0,rsm=0; void add(int x) { if(med==-1) { med=x; return; } if(x<=med) { lt.push(x); lsm+=x; } else { rt.push(x); rsm+=x; } if(lt.size()+1 < rt.size()) { // right has more elements ll y=rt.top(); rt.pop(); rsm-=y; swap(y,med); lsm+=y; lt.push(y); } if(rt.size()+1 < lt.size()) { ll y=lt.top(); lt.pop(); lsm-=y; swap(y,med); rsm+=y; rt.push(y); } // x+1 x // x x // x+1 x-1 } long long getsum() { return 1ll*lt.size()*med - lsm + rsm - 1ll*rt.size()*med; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int k,n; cin>>k>>n; ll ans=0; vector<ll> tp; pair<ll,ll> b[n+1]={}; vector<pair<ll,ll>> a; for(int i=0;i<n;i++) { char c,p; int x,y; cin>>c>>x>>p>>y; if(x>y)swap(x,y); if(c==p) { ans+=y-x; } else { ans+=1; tp.pb(x); tp.pb(y); b[i].first=x; b[i].second=y; a.pb({x+y,i}); } } int sz=tp.size(); if(!sz) { cout<<ans<<endl; return 0; } sort(begin(tp),end(tp)); sort(begin(a),end(a)); if(k==1) { for(auto i:tp) { ans+=abs(tp[sz/2]-i); } cout<<ans<<endl; return 0; } sz=a.size(); vector<long long> pre(sz+1); for(int i=0;i<sz;i++) { add(b[a[i].second].first); add(b[a[i].second].second); pre[i+1]=getsum(); } med=-1; lsm=0,rsm=0; while(lt.size())lt.pop(); while(rt.size())rt.pop(); ll mi=1e18; for(int i=sz-1;i>=0;i--) { add(b[a[i].second].first); add(b[a[i].second].second); mi=min(mi,getsum()+pre[i]); } cout<<ans+mi<<endl; }
#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...