Submission #466663

#TimeUsernameProblemLanguageResultExecution timeMemory
466663cgiosyPalembang Bridges (APIO15_bridge)C++17
100 / 100
85 ms5424 KiB
#include <bits/stdc++.h> using namespace std; using ll=long long; struct pii { int l, r; bool operator<(pii b) const { return l+r<b.l+b.r; } }; int main() { ios::sync_with_stdio(0);cin.tie(0); int K, N, M=0; cin>>K>>N; pii A[N]; ll B[N], s=0, w=0; for(int i=0; i<N; i++) { char a, b; int l, r; cin>>a>>l>>b>>r; if(l>r) swap(l, r); if(a!=b) A[M++]={l, r}; else s+=r-l; } s+=N=M; sort(A, A+N); priority_queue<int> L; priority_queue<int, vector<int>, greater<int>> R; auto add=[&](pii v) { L.push(v.l), R.push(v.r); w+=v.r-v.l; while(L.top()>R.top()) { int l=L.top(), r=R.top(); L.pop(), R.pop(); L.push(r), R.push(l); w+=(l-r)*2; } return w; }; for(int i=0; i<N; i++) B[i]=add(A[i]); w=0; decltype(L)().swap(L); decltype(R)().swap(R); ll t=N ? B[N-1] : 0; if(K==2 && N) for(int i=N; --i;) t=min(t, add(A[i])+B[i-1]); cout<<s+t<<'\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...