This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
int k,n;
long long sumL=0,sumU=0;
vector<ii>v;
multiset<int>low;
multiset<int>up;
long long pref[100005];
bool cmp(ii a,ii b)
{
return (a.fi+a.se)<(b.fi+b.se);
}
void capnhat(int x)
{
int val;
if(low.size()==0)val=1000000007;
else val=*low.rbegin();
if(x<=val){
low.insert(x);
sumL+=x;
}
else{
up.insert(x);
sumU+=x;
}
if(low.size()>up.size()+1){
up.insert(*low.rbegin());
sumU+=(*low.rbegin());
sumL-=(*low.rbegin());
low.erase(low.find(*low.rbegin()));
}
else if(up.size()>low.size()){
low.insert(*up.begin());
sumL+=(*up.begin());
sumU-=(*up.begin());
up.erase(up.find(*up.begin()));
}
}
main()
{
cin>>k>>n;
long long delt=0;
for(int i=1;i<=n;i++){
char a,b;
int x,y;
cin>>a>>x>>b>>y;
if(a==b){
delt+=abs(x-y);
}
else{
v.push_back({x,y});
}
}
sort(v.begin(),v.end(),cmp);
long long ans=LLONG_MAX;
for(int i=0;i<v.size();i++){
capnhat(v[i].fi);
capnhat(v[i].se);
pref[i]=sumU-sumL;
}
ans=min(ans,sumU-sumL+(long long)v.size());
if(k==2){
sumL=0,sumU=0;
low.clear();
up.clear();
for(int i=v.size()-1;i>0;i--){
capnhat(v[i].fi);
capnhat(v[i].se);
ans=min(ans,pref[i-1]+sumU-sumL+(long long)v.size());
}
}
cout<<ans+delt;
return 0;
}
Compilation message (stderr)
bridge.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main()
| ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
# | 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... |