제출 #380505

#제출 시각아이디문제언어결과실행 시간메모리
380505jass921026Palembang Bridges (APIO15_bridge)C++14
0 / 100
6 ms492 KiB
#include<bits/stdc++.h> using namespace std; #define jizz ios_base::sync_with_stdio(false);cin.tie(NULL); typedef long long ll; typedef pair<int,int> pii; #define F first #define S second #define ALL(x) (x).begin(),(x).end() #define pb push_back #define mkp make_pair bool cmp(pii a, pii b){ return a.F+b.F<a.S+b.S; } int abs(int x){ return x>0?x:-x; } vector<pii> segs; vector<int> pos; int main(){ jizz int k, n; cin>>k>>n; ll tmp=0; for(int i=0;i<n;i++){ char p, q; int s, t; cin>>p>>s>>q>>t; if(s>t) swap(s,t); tmp+=(t-s); if(p!=q) { tmp++; segs.pb(mkp(s,t)); pos.pb(s); pos.pb(t); } } ll ans1=tmp, ans2=tmp; if(pos.empty()){ cout<<tmp<<"\n"; return 0; } sort(ALL(pos)); sort(ALL(segs),cmp); int sz=segs.size(); int bp=pos[sz]; for(int i=0;i<sz;i++){ if(segs[i].S<bp) ans1+=2*(bp-segs[i].S); else if(segs[i].F>bp) ans1+=2*(segs[i].F-bp); } int idx=0; for(int i=0;i<sz;i++){ ll res=tmp; int cut=(segs[i].F+segs[i].S)/2; while(idx<2*sz&&pos[idx]<cut) idx++; int bp1=idx/2, bp2=(2*sz+idx)/2; for(int j=0;j<sz;j++){ if(j<i){ if(segs[i].S<bp1) res+=2*(bp1-segs[i].S); else if(segs[i].F>bp1) res+=2*(segs[i].F-bp1); } else{ if(segs[i].S<bp2) res+=2*(bp2-segs[i].S); else if(segs[i].F>bp2) res+=2*(segs[i].F-bp2); } } //cout<<i<<" "<<res<<"\n"; ans2=min(ans2,res); } if(k==1) cout<<ans1<<"\n"; else cout<<min(ans1,ans2)<<"\n"; return 0; } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */
#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...