#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
#define fi first
#define se second
typedef pair<int, int> ii;
int same, res, n, lsum, rsum, pre[N];
vector<ii> vec;
priority_queue<int> lq;
priority_queue<int, vector<int>, greater<int>> rq;
void add(int x){
//cout << x << "\n";
int tp = 1e18;
if (lq.size()) tp = lq.top();
if (x <= tp){
lq.push(x);
lsum += x;
}
else {
rq.push(x);
rsum += x;
}
if (rq.size() + 1 < lq.size()){
tp = lq.top();
lq.pop();
rq.push(tp);
rsum += tp;
lsum -= tp;
}
if (lq.size() < rq.size()){
tp = rq.top();
rq.pop();
lq.push(tp);
rsum -= tp;
lsum += tp;
}
}
bool cmp(ii& a, ii& b){
return a.fi + a.se < b.fi + b.se;
}
int k;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> k >> n;
for (int i = 1; i <= n; i++){
char aa, bb;
int pos1, pos2;
cin >> aa >> pos1 >> bb >> pos2;
if (aa == bb){
same += abs(pos2 - pos1);
}
else{
vec.push_back({pos1, pos2});
}
}
sort(vec.begin(), vec.end(), cmp);
same += vec.size();
for (int i = 1; i <= (int) vec.size(); i++){
add(vec[i - 1].fi);
add(vec[i - 1].se);
//cout << rsum << " " << lsum << "\n";
pre[i] = rsum - lsum;
}
res = pre[vec.size()];
if (k == 2){
lsum = rsum = 0;
while (lq.size()) lq.pop();
while (rq.size()) rq.pop();
for (int i = (int) vec.size(); i >= 1; i--){
add(vec[i - 1].fi);
add(vec[i - 1].se);
res = min(res, pre[i - 1] + rsum - lsum);
}
}
cout << res + same;
return 0;
}
# |
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 |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
352 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 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 |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
472 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
20 ms |
6888 KB |
Output is correct |
13 |
Correct |
43 ms |
7628 KB |
Output is correct |
14 |
Correct |
34 ms |
6344 KB |
Output is correct |
15 |
Correct |
24 ms |
5072 KB |
Output is correct |
16 |
Correct |
24 ms |
7060 KB |
Output is correct |
17 |
Correct |
30 ms |
7884 KB |
Output is correct |
18 |
Correct |
29 ms |
7116 KB |
Output is correct |
19 |
Correct |
35 ms |
7884 KB |
Output is correct |
20 |
Correct |
27 ms |
7376 KB |
Output is correct |
21 |
Correct |
34 ms |
7640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 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 |
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 |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 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 |
344 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 |
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 |
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 |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 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 |
516 KB |
Output is correct |
23 |
Correct |
1 ms |
544 KB |
Output is correct |
24 |
Correct |
1 ms |
356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
352 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 |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
352 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
352 KB |
Output is correct |
10 |
Correct |
1 ms |
344 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 |
504 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 |
352 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
352 KB |
Output is correct |
19 |
Correct |
1 ms |
356 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
352 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
29 ms |
6512 KB |
Output is correct |
26 |
Correct |
56 ms |
6596 KB |
Output is correct |
27 |
Correct |
65 ms |
7460 KB |
Output is correct |
28 |
Correct |
69 ms |
7912 KB |
Output is correct |
29 |
Correct |
67 ms |
7592 KB |
Output is correct |
30 |
Correct |
35 ms |
4044 KB |
Output is correct |
31 |
Correct |
31 ms |
6872 KB |
Output is correct |
32 |
Correct |
50 ms |
7888 KB |
Output is correct |
33 |
Correct |
49 ms |
7888 KB |
Output is correct |
34 |
Correct |
59 ms |
7624 KB |
Output is correct |
35 |
Correct |
34 ms |
7384 KB |
Output is correct |
36 |
Correct |
55 ms |
7696 KB |
Output is correct |
37 |
Correct |
24 ms |
6356 KB |
Output is correct |