Submission #1198607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198607		tawwie	Art Exhibition (JOI18_art)	C++20	100 / 100	142 ms	15952 KiB

art

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

int main(){
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    int n; cin >> n;
    vector<pair<ll, ll>> v(n+1); // pval = prefix sum val
    for(int i=1; i<=n; i++){
        ll a, b; cin >> a >> b; v[i] = {a, b};
    }
    sort(v.begin(), v.end());
    vector<ll> pval(n+1, 0), sz(n+1, 0);
    for(int i=1; i<=n; i++){
        sz[i] = v[i].first; pval[i] = pval[i-1] + v[i].second;
    }
    /*
    idea: work in ranges, if a_i and a_j was picked, 
    it makes sense to pick all the paintings with sizes inbetween i and j
    so it's now essentially a prefix sum problem
    find max(pval[j] - pval[i-1] - (sz[j] - sz[i]))
    = (pval[j] - sz[j]) - (pval[i-1] - sz[i])
    and if we iterate j, it now turns into "just keep the best (min) pval[i-1] - sz[i]"
    */
    ll ans = -1, mni = 1e18;
    for(int i=1; i<=n; i++){
        mni = min(mni, pval[i-1] - sz[i]);
        ans = max(ans, pval[i] - sz[i] - mni);
        //cout << ans << ' ';
    }
    cout << ans;
    return 0;
}

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