제출 #380522

#제출 시각아이디문제언어결과실행 시간메모리
380522jass921026Palembang Bridges (APIO15_bridge)C++14
63 / 100
2077 ms4200 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+a.S<b.F+b.S; } int abs(int x){ return x>0?x:-x; } vector<pii> segs; vector<int> pos, pos2; 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 ans=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) ans+=2*(bp-segs[i].S); else if(segs[i].F>bp) ans+=2*(segs[i].F-bp); } if(k==1){ cout<<ans<<"\n"; return 0; } ll ans2=ans; for(int i=0;i<sz;i++){ ll res=tmp; pos.clear(); pos2.clear(); for(int j=0;j<sz;j++){ if(j<=i){ pos.pb(segs[j].F); pos.pb(segs[j].S); } else{ pos2.pb(segs[j].F); pos2.pb(segs[j].S); } } sort(ALL(pos)); sort(ALL(pos2)); int bp1=pos[pos.size()/2], bp2=pos2[pos2.size()/2]; //cout<<bp1<<" "<<bp2<<"\n"; for(int j=0;j<sz;j++){ if(j<=i){ if(segs[j].S<bp1) res+=2*(bp1-segs[j].S); else if(segs[j].F>bp1) res+=2*(segs[j].F-bp1); } else{ if(segs[j].S<bp2) res+=2*(bp2-segs[j].S); else if(segs[j].F>bp2) res+=2*(segs[j].F-bp2); } } //cout<<i<<" "<<res<<"\n"; ans2=min(ans2,res); } cout<<min(ans,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 2 3 A 3 B 3 A 4 B 4 A 5 B 5 */
#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...