This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)});
}
}
ans += cross.size();
if(K==1) cout<<ans+one();
else cout<<ans+two();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |