#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
long long n,k,fakeres,ps[maxn],suf[maxn];
vector<pair<long long,long long>>all;
bool cmp(pair<long long,long long>a,pair<long long,long long>b){
return a.first+a.second<b.first+b.second;
}
void vorod(){
cin>>k>>n;
for(long long i=0;i<n;i++){
char c,cc;
long long d,dd;
cin>>c>>d>>cc>>dd;
if(d>dd){
swap(d,dd);
}
if(c==cc){
fakeres+=abs(dd-d);
}else{
all.push_back(make_pair(d,dd));
fakeres++;
}
}
n=(long long)all.size();
}
void pre(){
sort(all.begin(),all.end(),cmp);
priority_queue<long long>kam;
long long sumkam=0,sumziad=0;
for(long long i=0;i<n;i++){
kam.push(all[i].first);
kam.push(all[i].second);
sumkam+=all[i].first+all[i].second;
sumkam-=kam.top();
sumziad+=kam.top();
kam.pop();
ps[i]=sumziad-sumkam;
}
while((long long)kam.size()>0){
kam.pop();
}
sumkam=0,sumziad=0;
for(long long i=n-1;i>=0;i--){
kam.push(all[i].first);
kam.push(all[i].second);
sumkam+=all[i].first+all[i].second;
sumkam-=kam.top();
sumziad+=kam.top();
kam.pop();
suf[i]=sumziad-sumkam;
}
}
void solve(){
if(k==1){
long long mainres=fakeres+ps[n-1];
cout<<mainres<<"\n";
return ;
}
long long mainres=fakeres+suf[0];
for(long long i=0;i<n;i++){
mainres=min(mainres,fakeres+suf[i+1]+ps[i]);
}
cout<<mainres<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
644 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |