Submission #378248

#	Time	Username	Problem	Language	Result	Execution time	Memory
378248		jlallas384	Art Exhibition (JOI18_art)	C++17	100 / 100	825 ms	48468 KiB

art

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    vector<pair<ll,int>> a(n);
    for(auto &[sz,val]: a){
        cin >> sz >> val;
    }
    sort(a.begin(), a.end());
    vector<ll> b(n);
    multiset<ll> ms;
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += a[i].second;
        ll x = sum - (a[i].first - a[0].first);
        b[i] = x;
        ms.insert(x);
    }
    ll ans = *ms.rbegin(), pref = 0;
    for(int i = 1; i < n; i++){
        ms.erase(ms.find(b[i-1]));
        pref -= a[i-1].second;
        ans = max(ans, *ms.rbegin() + pref + (a[i].first - a[0].first));
    }
    cout << ans;
}

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