Submission #1187972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187972		alwaus424	Art Exhibition (JOI18_art)	C++20	100 / 100	320 ms	14044 KiB

art

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50