Submission #978417

#TimeUsernameProblemLanguageResultExecution timeMemory
978417nninPalembang Bridges (APIO15_bridge)C++17
22 / 100
34 ms4904 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> using ll = long long; #define f first #define s second vector<pii> cross; int N, K; ll check1(int bridge) { ll ret = 0; for(auto [st, en]:cross) { if(bridge<st) ret += (ll)st-bridge+en-bridge; else if(bridge>en) ret += (ll)bridge-st+bridge-en; else ret += (ll)en-st; } return ret; } ll check2(int br1, int br2) { ll ret = 0; for(auto [st, en]:cross) { if((st<=br1&&br1<=en) || (st<=br2&&br2<=en)) ret += (ll)en-st; else if(br2<st) ret += (ll)st-br2+en-br2; else if(br1>en) ret += (ll)br1-st+br1-en; else ret += min((ll)st-br1+en-br1, (ll)br2-st+br2-en); } return ret; } ll one() { vector<int> v; for(auto [st, en]:cross) { v.push_back(st); v.push_back(en); } sort(v.begin(), v.end()); return min(check1(v[((int)v.size()-1)/2]), check1(v[(int)v.size()/2])); } ll two() { vector<int> v; for(auto [st, en]:cross) { v.push_back(st); v.push_back(en); } sort(v.begin(), v.end()); int med1 = ((int)v.size()-1)/2; int med2 = (int)v.size()/2; set<int> l, r; l.insert(v[med1/2]); l.insert(v[(med1+1)/2]); l.insert(v[med2/2]); l.insert(v[(med2+1)/2]); r.insert(v[(med1+v.size()-1)/2]); r.insert(v[(med1+v.size())/2]); r.insert(v[(med2+v.size()-1)/2]); r.insert(v[(med2+v.size())/2]); ll ret = 1e18; for(int med1:l) for(int med2:r) { ret = min(ret, check2(med1, med2)); } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>K>>N; ll ans = 0; for(int i=0;i<N;i++) { char z1, z2; int b1, b2; cin>>z1>>b1>>z2>>b2; if(z1==z2) { ans += abs(b1-b2); } else { cross.push_back({min(b1, b2), max(b1, b2)}); } } if(cross.empty()) { cout<<ans; return 0; } ans += cross.size(); if(K==1) cout<<ans+one(); else cout<<ans+two(); }
#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...