#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll compute(ll sum,ll min,ll max){
return sum-(max-min);
}
int main(){
int n;
cin>>n;
vector<pair<ll,ll>> paintings(n);
for (int i=0;i<n;i++){
ll a,b;
cin>>a>>b;
paintings[i]={a,b};
}
sort(paintings.begin(),paintings.end());
int l=0;
int r=-1;
ll sum=0;
ll min=paintings[l].first;
ll maxx=0;
ll ans=0;
while (r<n-1){
r++;
sum+=paintings[r].second;
maxx=paintings[r].first;
//cout<<"now at: "<<r<<" sum is: "<<sum<<" and max is now "<<maxx<<" and min is "<<min<<"\n";
ans=max(ans,compute(sum,min,maxx));
while (l<r && compute(sum-paintings[l].second,paintings[l+1].first,maxx)>ans){
//cout<<"it's better if we exclude "<<l<<" because we will have "<<compute(sum-paintings[l].second,paintings[l+1].first,maxx)<<"\n";
sum-=paintings[l].second;
l++;
min=paintings[l].first;
}
ans=max(ans,compute(sum,min,maxx));
}
cout<<ans;
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... |