Submission #1188358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188358		dirtycodehehe	Art Exhibition (JOI18_art)	C++20	100 / 100	311 ms	12156 KiB

art

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n;
    cin >> n;
    vector<pair<int, int>> a(n); // {size, value}
    for(int i = 0; i < n; ++i){
        cin >> a[i].first >> a[i].second;
    }

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

    vector<int> prefix(n + 1);
    for(int i = 0; i < n; ++i){
        prefix[i + 1] = prefix[i] + a[i].second;
    }

    int ans = LLONG_MIN;
    int prefix_min = LLONG_MAX;

    for(int r = 0; r < n; ++r){
        int size_r = a[r].first;
        prefix_min = min(prefix_min, prefix[r] - a[r].first);
        ans = max(ans, (prefix[r + 1] - a[r].first) - prefix_min);
    }

    cout << ans << '\n';
}

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