//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
using ost = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define trav(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define pb push_back
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
// TOP > BOTTOM
multiset<ll, greater<ll>> top1, top2;
multiset<ll> bottom1, bottom2;
ll ts1, bs1, ts2, bs2;
void chk(multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
if ((int)top.size()-1 > (int)bottom.size()) {
ll temp = *top.begin(); top.erase(top.find(temp)); bottom.insert(temp);
ts-=temp; bs+=temp;
}
if ((int)bottom.size() > (int)top.size()) {
ll temp = *bottom.begin(); bottom.erase(bottom.find(temp)); top.insert(temp);
bs-=temp; ts+=temp;
}
}
void ins(ll x, multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
if (top.size()==0) {top.insert(x); ts+=x;}
else if (x>*top.begin()) {bottom.insert(x); bs+=x;}
else {top.insert(x); ts+=x;};
chk(top, bottom, ts, bs);
}
void re(ll x, multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
if (top.find(x) != top.end()) {top.erase(top.find(x)); ts-=x;}
else {bottom.erase(bottom.find(x)); bs-=x;}
chk(top, bottom, ts, bs);
}
ll calc(multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){
if (top.size()==0) return 0;
ll m = *top.begin();
return m*(top.size()) - ts - m*(bottom.size()) + bs;
}
int main(){
int n, k;
cin >> k >> n;
ll leftover = 0;
vl nums;
F0R(_, n){
char l1, l2;
ll n1, n2;
cin >> l1 >> n1 >> l2 >> n2;
if(l1==l2) leftover += abs(n2-n1);
else {
nums.pb(n1); nums.pb(n2);
}
}
leftover += nums.size()/2;
sort(all(nums));
if(k==1){
ll md = nums[nums.size()/2];
ll ans = 0;
trav(i, nums){
ans += abs(md-i);
}
cout << ans+leftover<< endl;
return 0;
}
trav(i, nums){
ins(i, top1, bottom1, ts1, bs1);
}
ll mn = LLONG_MAX;
trav(i, nums){
re(i, top1, bottom1, ts1, bs1);
ins(i, top2, bottom2, ts2, bs2);
mn = min(mn, calc(top1, bottom1, ts1, bs1)+calc(top2, bottom2, ts2, bs2));
}
cout << mn+leftover << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
2 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
45 ms |
2448 KB |
Output is correct |
13 |
Correct |
102 ms |
2408 KB |
Output is correct |
14 |
Correct |
71 ms |
2368 KB |
Output is correct |
15 |
Correct |
80 ms |
1348 KB |
Output is correct |
16 |
Correct |
76 ms |
2364 KB |
Output is correct |
17 |
Correct |
93 ms |
2452 KB |
Output is correct |
18 |
Correct |
84 ms |
2436 KB |
Output is correct |
19 |
Correct |
98 ms |
2364 KB |
Output is correct |
20 |
Correct |
91 ms |
2464 KB |
Output is correct |
21 |
Correct |
98 ms |
2540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 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 |
- |