Submission #152067

#TimeUsernameProblemLanguageResultExecution timeMemory
152067AS82Art Exhibition (JOI18_art)C++14
100 / 100
265 ms25028 KiB
//In the name of Allah
//Ya Ali!
#include <bits/stdc++.h>

using namespace std;
typedef long long ll ;

const ll maxn = 5000 * 101 ;
const ll INF = 1e18 ;

#define f first
#define s second

ll n , pre[maxn] , ans = 0 , maxx = 0 ;
vector<pair<ll,ll> > v ;

int main()
{
std::ios::sync_with_stdio(0) ;
cin.tie(0) ;
cout.tie(0) ;

cin >> n ;
for(int  i = 0 ; i < n ; i ++){
    ll a , b ;
    cin >> a >> b ;
    v.push_back({a,b}) ;
}

sort(v.begin() , v.end()) ;

pre[0] = v[0].s ;
for(int i = 1 ; i < n ;i ++)pre[i] = pre[i-1] + v[i].s ;

ans = pre[0] - v[0].f ;
maxx = v[0].f ;

for(int i = 1 ; i < n ; i ++){
    maxx = max(maxx , v[i].f - pre[i-1]) ;
    ans = max(ans , pre[i] - v[i].f + maxx) ;
}
cout << ans ;


 return 0;
}
/*
                  _     _   __
            /_\  (_    (_)  __)
           /   \  _) . (_) (__
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...