#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int k, n;
cin >> k >> n;
int m = n;
vector<tuple<int, int, int>> num;
vector<int> all;
int ans = 0;
for (int i = 0; i < n; i++) {
int a, b;
char c, d;
cin >> c >> a >> d >> b;
if (c == d) {
m--;
ans += abs(b-a);
} else {
ans++;
all.push_back(a);
all.push_back(b);
num.push_back({a+b, a, b});
}
}
sort(all.begin(), all.end());
if (k == 1) {
int x = all[all.size()/2];
for (int i : all) {
ans += abs(i-x);
}
cout << ans << endl;
} else {
sort(num.begin(), num.end());
multiset<int> rbig;
multiset<int> rsmall;
multiset<int> lbig;
multiset<int> lsmall;
int rbigsum = 0, lbigsum = 0, rsmallsum = 0, lsmallsum = 0;
for (int i = 0; i < all.size(); i++) {
if (i <= all.size()/2) {
rsmall.insert(all[i]);
rsmallsum += all[i];
} else {
rbig.insert(all[i]);
rbigsum += all[i];
}
}
auto it = rsmall.end(); it--;
int rmed = *it, lmed = 0;
int res = 1e9; //biggest
//~ cout << "YAYYYYY " << num.size() << endl;
for (int i = 0; i < m-1; i++) {
//~ cout << m << " " << i << endl;
int tmp = 0; //ans for now
auto [tot, a, b] = num[i];
//remove from right
if (a <= rmed) {
rsmall.erase(rsmall.find(a));
rsmallsum -= a;
} else {
rbig.erase(rbig.find(a));
rbigsum -= a;
}
if (b <= rmed) {
rsmall.erase(rsmall.find(b));
rsmallsum -= b;
} else {
rbig.erase(rbig.find(b));
rbigsum -= b;
}
//equalize right array lengths
if (rbig.size() > rsmall.size()) {
auto it = rbig.begin();
rsmall.insert(*it);
rbigsum -= *it;
rsmallsum += *it;
rbig.erase(rbig.begin());
}
if (rsmall.size() > rbig.size()) {
auto it = rsmall.end(); it--;
rbig.insert(*it);
rbigsum += *it;
rsmallsum -= *it;
rsmall.erase(it);
}
auto it = rsmall.end(); it--;
int rmed = *it;
//~ cout << "R DONE" << endl;
//add to left
if (a <= lmed) {
lsmall.insert(a);
lsmallsum += a;
} else {
lbig.insert(a);
lbigsum += a;
}
if (b <= rmed) {
lsmall.insert(b);
lsmallsum += b;
}
else {
lbig.insert(b);
lbigsum += b;
}
//equalize left array lengths
if (lbig.size() > lsmall.size()) {
auto it = lbig.begin();
lsmall.insert(*it);
lsmallsum += *it;
lbigsum -= *it;
lbig.erase(it);
}
if (lsmall.size() > lbig.size()) {
auto it = lsmall.end(); it--;
lbig.insert(*it);
lbigsum += *it;
lsmallsum -= *it;
lsmall.erase(it);
}
//calc left median
it = lsmall.end(); it--;
lmed = *it;
//~ cout << "L DONE" << endl;
//calc left sum
tmp += abs(lbigsum-lsmallsum);
//~ cout << lmed << ": " << tmp;
//calc right sum
tmp += abs(rbigsum-rsmallsum);
//update ans
res = min(res, tmp);
//~ cout << " AAA " << rmed << ": " << tmp << endl;
}
cout << res+ans << endl;
}
}
//change if to while if wa as may be multiple??
//changes infinities higher if wa
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:45:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
bridge.cpp:46:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if (i <= all.size()/2) {
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
536 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
464 KB |
Output is correct |
12 |
Correct |
18 ms |
5464 KB |
Output is correct |
13 |
Correct |
33 ms |
6752 KB |
Output is correct |
14 |
Correct |
26 ms |
5972 KB |
Output is correct |
15 |
Correct |
20 ms |
4208 KB |
Output is correct |
16 |
Correct |
22 ms |
6028 KB |
Output is correct |
17 |
Correct |
23 ms |
6740 KB |
Output is correct |
18 |
Correct |
26 ms |
6216 KB |
Output is correct |
19 |
Correct |
33 ms |
6644 KB |
Output is correct |
20 |
Correct |
21 ms |
6228 KB |
Output is correct |
21 |
Correct |
29 ms |
6484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
360 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |