#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'
bool cmp(pair<int,int> p1, pair<int,int> p2){
return p1.first+p1.second < p2.first+p2.second;
}
vector<pair<int,int>> v;
int n;
vector<int> func(){
vector<int> lc(n);
priority_queue<int> lo;
priority_queue<int, vector<int>, greater<int>> hi;
int ls = 0, rs = 0;
for(int i=0; i<n; i++){
auto [l, r] = v[i];
if(lo.empty() or l <= lo.top()) lo.push(l), ls += l;
else hi.push(l), rs += l;
if(lo.empty() or r <= lo.top()) lo.push(r), ls += r;
else hi.push(r), rs += r;
if(lo.size() > hi.size()){
int x = lo.top();
hi.push(x), rs += x;
lo.pop(), ls -= x;
}
else if(hi.size() > lo.size()){
int x = hi.top();
lo.push(x), ls += x;
hi.pop(), rs -= x;
}
int m = lo.top();
lc[i] = rs - ls;
}
return lc;
}
inline void solve(){
int k;
cin>>k>>n;
int ini = 0;
for(int i=0; i<n; i++){
char p, q;
int a, b;
cin>>p>>a>>q>>b;
if(p == q) ini += abs(a-b);
else ini++, v.push_back({min(a, b), max(a, b)});
}
n = v.size();
sort(v.begin(), v.end());
auto lc = func();
reverse(v.begin(), v.end());
auto rc = func();
int mn = min(lc[n-1], rc[n-1]);
for(int i=0; i<n-1; i++){
mn = min(mn, lc[i] + rc[n-i-2]);
}
cout<<ini + (k == 1 ? lc[n-1] : mn);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
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... |