Submission #1330322

#TimeUsernameProblemLanguageResultExecution timeMemory
1330322kasamchiArt Exhibition (JOI18_art)C++20
100 / 100
267 ms41536 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;

    vector<pair<long long, int>> artworks(N);
    for (int i = 0; i < N; i++) {
        cin >> artworks[i].first >> artworks[i].second;
    }
    sort(artworks.begin(), artworks.end());

    vector<long long> A(N + 1);
    vector<int> B(N + 1);
    for (int i = 1; i <= N; i++) {
        A[i] = artworks[i - 1].first;
        B[i] = artworks[i - 1].second;
    }

    vector<long long> pre(N + 1);
    for (int i = 1; i <= N; i++) {
        pre[i] = pre[i - 1] + B[i];
    }

    multiset<long long> ms;
    for (int i = 1; i <= N; i++) {
        ms.insert(pre[i] - A[i]);
    }

    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, A[i] - pre[i - 1] + *ms.rbegin());
        ms.erase(ms.find(pre[i] - A[i]));
    }
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...