| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 660015 | aebov | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
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<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<utility>
#include<unordered_map>
#include<vector>
#include<set>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
#define pb push_back
using namespace std;
const int N = (int)1e5 + 5, mod = (ll)1e9 + 7;
int n, k, x, y;
char ch, hc;
ll sm = 0, sm2 = (ll)1e18 + 18;
void sub(){
// cerr << "\n entered #sub 2 \n";
vector<int> cv;
vector<pii> vc; vc.pb({0,0});
for(int i = 1; i <= n; i ++){
cin >> ch >> x >> hc >> y;
if(x < y)swap(x, y);
if(ch == hc) sm += x - y;
else vc.pb({y, x});
} n = vc.size() - 1;
// cout << "N " << n << endl;
for(int i = 1; i <= n; i ++) {
cv.pb(vc[i].F);
cv.pb(vc[i].S);
}
sort(cv.begin(), cv.end());
// for(auto u : cv)cout << u << endl;
for(int i = 0; i < cv.size(); i ++){
for(int j = i; j < cv.size(); j ++) {
int x = cv[i], y = cv[j];
int sum = 0;
for(int z = 1; z <= n; z ++){
if(vc[z].S < x) sum += (x<<1) - vc[z].F - vc[z].S + 1;
else if(vc[z].F > y) sum += vc[z].F + vc[z].S - (y<<1) + 1;
else if(x < vc[z].F && vc[z].S < y)sum += min(vc[z].F + vc[z].S -(x<<1) + 1,(y<<1) - vc[z].F - vc[z].S + 1);
else sum += vc[z].S - vc[z].F + 1;
}
sm2 = min(sm2, sum);
}
}
// cout << sm << " " << sm2 << endl;
cout << sm + sm2 << endl;
exit(0);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> k >> n;
vector<int> vc;
if(k == 2 && n < 101)sub();
// cerr << "\n enteres #sub1 \n";
for(int i = 1; i <= n; i ++){
cin >> ch >> x >> hc >> y;
if(ch == hc) sm += abs(x - y);
else sm ++, vc.pb(x), vc.pb(y);
}
sort(vc.begin(), vc.end());
int pos = vc[(vc.size() - 1) / 2];
for(auto x : vc)sm += abs(x - pos);
cout << sm << endl;
}