제출 #332359

#제출 시각아이디문제언어결과실행 시간메모리
332359limabeansArt Exhibition (JOI18_art)C++17
100 / 100
363 ms50924 KiB
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;
const ll inf = 1e18;



ll S[maxn], A[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n;
    cin>>n;
    vector<pair<ll,ll>> a(n);
    for (int i=0; i<n; i++) {
	cin>>a[i].first>>a[i].second;
    }

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

    for (int i=0; i<n; i++) {
	S[i+1] = S[i]+a[i].second;
	A[i+1] = a[i].first;
    }

    set<ll> st;


    ll hi = -inf;
    
    for (int i=1; i<=n; i++) {
	ll cur = S[i]-A[i];
	st.insert(A[i]-S[i-1]);
	cur += *st.rbegin();
	hi = max(hi, cur);
    }

    cout<<hi<<endl;
    
    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...