#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e5 + 7;
constexpr ll oo = 2e18;
ll total;
ll pref[MAXN];
vector<pair<ll, ll>> T;
priority_queue<ll> lefts, rights;
ll sumL, sumR;
int n, k, D;
bool cmp(pair<ll, ll> a, pair<ll, ll> b){
return a.first + a.second < b.first + b.second;
}
void medianAdd(ll x){
ll median = (lefts.size()? lefts.top(): oo);
if(x <= median){
lefts.push(x);
sumL += x;
}
else{
rights.push(-x);
sumR += x;
}
if(lefts.size() < rights.size()){
ll nxt = -(rights.top());
rights.pop();
sumR -= nxt;
lefts.push(nxt);
sumL += nxt;
}
if(rights.size() + 1 < lefts.size()){
ll nxt = lefts.top();
lefts.pop();
sumL -= nxt;
rights.push(-nxt);
sumR += nxt;
}
}
void queueclear(){
while(lefts.size()) lefts.pop();
while(rights.size()) rights.pop();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 1; i <= n; i++){
char x, y;
ll a, b;
cin >> x >> a >> y >> b;
if(b < a) swap(a, b);
if(x != y) T.push_back({a, b});
else total += (b-a);
}
sort(T.begin(), T.end(), cmp);
D = T.size();
total += D;
for(int i = 1; i <= D; i++){
medianAdd(T[i-1].first);
medianAdd(T[i-1].second);
pref[i] = abs(sumL - sumR);
}
ll best = pref[D];
if(k == 2){
sumL = sumR = 0;
queueclear();
for(int i = D; i > 0; i--){
medianAdd(T[i-1].first);
medianAdd(T[i-1].second);
best = min(best, pref[i-1] + abs(sumL-sumR));
}
}
cout << total + best << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
472 KB |
Output is correct |
| 4 |
Correct |
1 ms |
472 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 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 |
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 |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
372 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
20 ms |
6356 KB |
Output is correct |
| 13 |
Correct |
40 ms |
7628 KB |
Output is correct |
| 14 |
Correct |
31 ms |
6356 KB |
Output is correct |
| 15 |
Correct |
23 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
20 ms |
7296 KB |
Output is correct |
| 17 |
Correct |
34 ms |
7808 KB |
Output is correct |
| 18 |
Correct |
23 ms |
7632 KB |
Output is correct |
| 19 |
Correct |
39 ms |
8140 KB |
Output is correct |
| 20 |
Correct |
27 ms |
7624 KB |
Output is correct |
| 21 |
Correct |
39 ms |
7628 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 |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
788 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
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 |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
512 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
516 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
468 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
600 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
500 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
868 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
32 ms |
6348 KB |
Output is correct |
| 26 |
Correct |
47 ms |
6864 KB |
Output is correct |
| 27 |
Correct |
63 ms |
7884 KB |
Output is correct |
| 28 |
Correct |
65 ms |
8388 KB |
Output is correct |
| 29 |
Correct |
70 ms |
8648 KB |
Output is correct |
| 30 |
Correct |
33 ms |
4556 KB |
Output is correct |
| 31 |
Correct |
27 ms |
7404 KB |
Output is correct |
| 32 |
Correct |
55 ms |
7880 KB |
Output is correct |
| 33 |
Correct |
37 ms |
7624 KB |
Output is correct |
| 34 |
Correct |
64 ms |
7892 KB |
Output is correct |
| 35 |
Correct |
38 ms |
7628 KB |
Output is correct |
| 36 |
Correct |
57 ms |
7624 KB |
Output is correct |
| 37 |
Correct |
23 ms |
6356 KB |
Output is correct |
