#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
struct median{
multiset<int, greater<int> > low;
multiset<int> high;
ll sum_low = 0, sum_hight = 0;
void add(int x){
if(low.empty() || *low.begin() > x){
low.insert(x);
sum_low += x;
}
else{
high.insert(x);
sum_hight += x;
}
while(low.size() > high.size() + 1){
int v = *low.begin();
low.erase(low.begin());
high.insert(v);
sum_low -= v;
sum_hight += v;
}
while(low.size() < high.size()){
int v = *high.begin();
high.erase(high.begin());
low.insert(v);
sum_low += v;
sum_hight -= v;
}
}
ll sum_median(){
return low.empty() ? 0LL : 1LL * *low.begin() * low.size() - sum_low + sum_hight - 1LL * *low.begin() * high.size();
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> k >> n;
vector<pair<int, int> > a;
ll temp = 0, res = 0;
char c1, c2;
for(int i = 0, s, f; i < n; ++ i){
cin >> c1 >> s >> c2 >> f;
if(s > f) swap(s, f);
if(c1 == c2) temp += f - s;
else{
temp ++;
a.emplace_back(s, f);
}
}
if(n == 0){
cout << temp;
return 0;
}
n = (int)a.size();
sort(a.begin(), a.end(), [&](pair<int, int>r, pair<int,int>l){return r.first + r.second < l.first + l.second;});
vector<ll> pref(n);
median md;
for(int i = 0; i < n; ++ i){
md.add(a[i].first);
md.add(a[i].second);
pref[i] = md.sum_median();
}
res = pref.back();
if(k == 2){
median dm;
for(int i = n - 1; i > 0; -- i){
dm.add(a[i].first);
dm.add(a[i].second);
res = min(res, dm.sum_median() + pref[i-1]);
}
}
res += temp;
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |