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 pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
int k, n;
ll ans = 0;
vl ord;
ll pos[100100][2];
int main(){
ios_base::sync_with_stdio(false);
cin>>k>>n;
memset(pos, -1, sizeof pos);
for(int i = 0; i < n; i++){
char side1, side2;
ll p1, p2;
cin>>side1>>p1>>side2>>p2;
if(side1 == side2){
ans += abs(p1 - p2);
}
else
{
pos[i][0] = p1;
pos[i][1] = p2;
ord.pb(p1);
ord.pb(p2);
}
}
sort(ord.begin(), ord.end());
int sz = (int)ord.size();
if(ord.size() > 0 && k == 1){
ll pref[sz];
pref[0] = ord[0];
for(int i = 1; i < sz; i++)
pref[i] = pref[i-1] + ord[i];
ll best = 1e18;
for(int i = 0; i < sz; i++){
ll here = ans;
if(i+1 < sz)
{
here += pref[sz-1];
here -= pref[i];
here -= (sz - 1 - i) * ord[i];
}
if(i){
here -= pref[i-1];
here += i * ord[i];
}
here += (int)ord.size()/2;
best = min(best, here);
}
cout<<best<<endl;
return 0;
}
else if(ord.size() > 0 && k == 2){
ll best = 1e18;
for(int i = 0; i < n; i++){
if(pos[i][0] == pos[i][1]) continue;
int l = min(pos[i][0], pos[i][1]), r = max(pos[i][0], pos[i][1]);
ll here = ans + 1 + r - l;
for(int j = 0; j < n; j++){
if(pos[j][0] == -1 || i == j) continue;
ll mn = min(pos[j][0], pos[j][1]), mx = max(pos[j][0], pos[j][1]);
if(mx <= l) here += 2 * l - mx - mn + 1;
else if(mn >= r) here += mx + mn - 2*r + 1;
else if(mn <= l && mx >= r) here += mx - mn + 1;
else if(mn <= l && mx <= r) here += mx - mn + 1;
else if(mn <= r && r <= mx) here += mx - mn + 1;
else if(l <= mn && mx <= r){
ll small = mn + mx - 2 * l + 1, big = 2 * r - mn - mx + 1;
here += min(small, big);
}
}
best = min(best,here);
}
cout<<best<<endl;
return 0;
}
cout<<ans<<endl;
return 0;
}
# | 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... |