Submission #1187976

#TimeUsernameProblemLanguageResultExecution timeMemory
1187976alwaus424Art Exhibition (JOI18_art)C++20
100 / 100
316 ms12228 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

    vector<pair<long long, long long>> artworks(n);
    for (int i = 0; i < n; ++i) {
        cin >> artworks[i].first >> artworks[i].second; // {size, value}
    }

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

    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + artworks[i].second;
    }

    long long max_diff = LLONG_MIN;
    long long prefix_min = LLONG_MAX;

    for (int r = 0; r < n; ++r) {
        long long size_r = artworks[r].first;
        prefix_min = min(prefix_min, prefix[r] - size_r);
        max_diff = max(max_diff, (prefix[r + 1] - size_r) - prefix_min);
    }

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