#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 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)1e9 + 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];
ll 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;
}
Compilation message
bridge.cpp: In function 'void sub()':
bridge.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < cv.size(); i ++){
| ~~^~~~~~~~~~~
bridge.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = i; j < cv.size(); j ++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
