Submission #840513

#TimeUsernameProblemLanguageResultExecution timeMemory
840513overwatch9Art Exhibition (JOI18_art)C++17
0 / 100
0 ms212 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
vector <pair <ll, ll>> pnts;
int main() {
    int n;
    cin >> n;
    pnts.resize(n+1);
    for (int i = 1; i <= n; i++)
        cin >> pnts[i].first >> pnts[i].second;
    sort(pnts.begin() + 1, pnts.end());
    for (int i = 2; i <= n; i++)
        pnts[i].second += pnts[i-1].second;
    ll ans = pnts[1].second;
    int l = 1, r = 1;
    for (int i = 2; i <= n; i++) {
        ans = max(ans, pnts[i].second - pnts[i-1].second);
        ll added_diff = pnts[i].first - pnts[r].first;
        ll added_val = pnts[i].second - pnts[r].first;
        if (added_val >= added_diff) {
            ans = max(ans, (pnts[i].second - pnts[l-1].second) - (pnts[i].first - pnts[l].first));
            r = i;
        } else if (l+1 <= r) {
            added_diff -= (pnts[l+1].first - pnts[l].first);
            added_val -= (pnts[l].second - pnts[l-1].second);
            if (added_val >= added_diff) {
                ans = max(ans, (pnts[i].second - pnts[l].second) - (pnts[i].first - pnts[l+1].first));
                l++;
            }
        }
    }
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...