Submission #1369976

#TimeUsernameProblemLanguageResultExecution timeMemory
1369976c12Art Exhibition (JOI18_art)C++20
100 / 100
267 ms8240 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {
    int n;
    cin >> n;

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

    ll best = LLONG_MIN;
    ll sum = 0;
    ll mx = 0;
    for(int i = 0;i < n;i++){
        ll pre = sum + vec[i].second;
        best = max(best,vec[i].first - sum);
        mx = max(mx,pre - vec[i].first + best);
        sum = pre;
    }
    cout << mx;
}
/*
S - A[i] + A[j]
Pre[i] - pre[j-1] - A[i] + A[j]
pre[i] - A[i] + max( - pre[j-1] + A[j])
*/
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...