제출 #152067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152067		AS82	Art Exhibition (JOI18_art)	C++14	100 / 100	265 ms	25028 KiB

art

//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;
}
/*
                  _     _   __
            /_\  (_    (_)  __)
           /   \  _) . (_) (__
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50