Submission #1095400

#TimeUsernameProblemLanguageResultExecution timeMemory
1095400sunflowerArt Exhibition (JOI18_art)C++14
100 / 100
128 ms20920 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

#define sz first
#define val second

const int maxn = (int) 5e5 + 7;

pair <long long, long long> a[maxn + 2];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n) cin >> a[i].sz >> a[i].val;

    sort(a + 1, a + 1 + n);

    a[0].val = 0;
    FOR(i, 1, n) a[i].val += a[i - 1].val;

    ll pref = 0, ans = 0;
    // a[j].val - a[i - 1].val  - (a[j].sz - a[i].sz) is maximize;
    // a[j].val - a[j].sz - (a[i - 1].val - a[i].sz);

    FOR(i, 1, n) {
        minimize(pref, a[i - 1].val - a[i].sz);
        maximize(ans, a[i].val - a[i].sz - pref);
    }

    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...