Submission #970984

#TimeUsernameProblemLanguageResultExecution timeMemory
970984shezittArt Exhibition (JOI18_art)C++14
50 / 100
3 ms788 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <queue>
#include <set>

using namespace std;

using ll = long long;

#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define ii pair<int,int>
#define F first
#define S second

const int MAXN = 5050;

int n;
ii arr[MAXN];
int sum[MAXN];

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

    cin >> n;

    fore(i, 0, n){
        cin >> arr[i].F >> arr[i].S;
    }

    sort(arr, arr+n, [](ii u, ii v) -> bool {
        if(u.F == v.F){
            return u.S < v.S;
        }
        return u.F < v.F;
    });

    fore(i, 0, n){
        sum[i+1] = sum[i] + arr[i].S;
    }

    int ans = 0;

    set<int> st;
    fore(j, 0, n){
        st.insert(arr[j].F - sum[j]);
        int res = sum[j+1] - arr[j].F;
        res += *st.rbegin();
        ans = max(ans, res);
    }

    cout << ans;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...