Submission #1187967

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

art

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Artwork {
    long long size;
    long long value;
};

bool compareArtworks(const Artwork& a, const Artwork& b) {
    return a.size < b.size;
}

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

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

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

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

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

    for (int r = 0; r < n; ++r) {
        prefix_min = min(prefix_min, prefix_sums[r] - artworks[r].size); // P[l-1] - A[l]
        max_diff = max(max_diff, (prefix_sums[r + 1] - artworks[r].size) - prefix_min); // (P[r] - A[r]) - min(P[l-1] - A[l])
    }

    cout << max_diff << endl;

    return 0;
}

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