/*
Author: ArifKraw
Rating: 1379
Goal#1: Beat I_Love_Trott ))))
Goal#2: Not to allow FractalFrog beat myself
*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ll long long
#define ld long double
#define nl '\n'
const ll N = 5e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const ld pi = 3.141592653589793;
const ld eps = 1e-12;
const ll zero = 0;
const int MAX = 1e6+5;
const int A = 1e9 + 5;
/*if you cant solve the problem:
try optimized(clever) brute-force;
try prefix sums with/or binary search
try dp
try dfs
try to solve in reversed orderr
try math
try to sort(sort(a+1,a+1+n)
int overflow, array bounds
think about special cases( n=1?)
*/
ll xx1[8]={0, 0,-1, 1, 1,-1, 1,-1};
ll xx2[8]={1,-1, 0, 0, 1, 1,-1,-1};
pair<ll,ll> a[N];
void egoist(){
ll n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].ff>>a[i].ss;
}
sort(a+1,a+n+1);
ll mx=0;
ll val=0,pos2=0,val2=0;
for(int i=1;i<=n;i++){
val=a[i].ff;
val2-=a[i-1].ss;
mx=max(val2+val-a[min(pos2,n)].ff,mx);
while(pos2<=i){
val2+=a[pos2].ss;
pos2++;
}
while(pos2<=n){
if(val+val2+a[pos2].ss-a[pos2].ff>=0){
val2+=a[pos2].ss;
mx=max(val2+val-a[min(pos2,n)].ff,mx);
pos2++;
}
else{
break;
}
}
mx=max(val2+val-a[min(pos2,n)].ff,mx);
}
mx=max(val+val2-a[n].ff,mx);
cout<<mx;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("sparse.in", "r", stdin);
//freopen("sparse.out", "w", stdout);
egoist();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
