제출 #1325604

#제출 시각아이디문제언어결과실행 시간메모리
1325604pramad712Art Exhibition (JOI18_art)C++17
100 / 100
130 ms16220 KiB
#include <bits/stdc++.h>
using namespace std;

struct Artwork {
    long long size, value;

    bool operator < (const Artwork &other) const {
        return size < other.size;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int length;
    cin >> length;

    vector works = {Artwork{0, 0}};

    for (int index = 0; index < length; index++) {
        long long size, value;
        cin >> size >> value;

        works.push_back(Artwork{size, value});
    }

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

    vector<long long> prefix_value_sums;
    long long total = 0;

    for (Artwork work: works) {
        total += work.value;
        prefix_value_sums.push_back(total);
    }

    vector<long long> suffix_maximas(length + 1);
    suffix_maximas.back() = prefix_value_sums.back() - works.back().size;

    for (int index = length - 1; index > 0; index--) {
        suffix_maximas[index] = max(suffix_maximas[index + 1], prefix_value_sums[index] - works[index].size);
    }

    long long maxima = -1LL;

    for (int index = 1; index <= length; index++) {
        maxima = max(maxima, works[index].size - prefix_value_sums[index - 1] + suffix_maximas[index]);
    }

    cout << maxima << "\n";
    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...