Submission #1187972

#TimeUsernameProblemLanguageResultExecution timeMemory
1187972alwaus424Art Exhibition (JOI18_art)C++20
100 / 100
320 ms14044 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

    vector<long long> size(n), value(n);
    for (int i = 0; i < n; ++i) {
        cin >> size[i] >> value[i];
    }

    // Sort by size using indices
    vector<int> idx(n);
    for (int i = 0; i < n; ++i) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return size[a] < size[b];
    });

    vector<long long> prefix_sums(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sums[i + 1] = prefix_sums[i] + value[idx[i]];
    }

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

    for (int r = 0; r < n; ++r) {
        long long curr_size = size[idx[r]];
        long long curr_prefix = prefix_sums[r];
        prefix_min = min(prefix_min, curr_prefix - curr_size);
        max_diff = max(max_diff, (prefix_sums[r + 1] - curr_size) - 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...