#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll, ll>> v;
ll sz(int idx){
return v[idx].first;
}
ll val(int idx){
return v[idx].second;
}
int main(){
cin.tie(NULL)->ios_base::sync_with_stdio(false);
int n; cin >> n;
for(int i=0; i<n; i++){
ll a, b; cin >> a >> b;
v.push_back({a, b}); // sz, val
}
sort(v.begin(), v.end());
//for(auto [i, j] : v) cout << i << ' ' << j << '\n';
// deque is actually overkill for this task
// a two pointer approach with sliding window is all it takes
// my main intuition was correct, just the implementation was a bit wonky
ll ans = 0, s = 0; int l = 0;
//deque<pair<ll, int>> dq; dq.push_back({sz(0), l}); s += val(0); // {size, index}
for(int r=0; r<n; r++){
s += val(r);
while(l < r){
if(s - (sz(r) - sz(l)) < s - val(l) - (sz(r) - sz(l + 1))){
s -= val(l); l++;
}else{
break;
}
}
ans = max(ans, s - (sz(r) - sz(l)));
}
cout << ans;
return 0;
}
/*
15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562
*/
# | 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... |