Submission #1302682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302682		hectormedrano	Art Exhibition (JOI18_art)	C++20	100 / 100	422 ms	16072 KiB

art

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

int main() {
	ll N, ans;
    cin>>N;
    vector<ll> S(N+1), MX(N+1);
    vector<pair<ll, ll>> AB(N+1);
    AB[0].first = AB[0].second = 0;
    MX[N] = ans = -1e18;
    for(ll i=1;i<=N;i++){
        cin>>AB[i].first>>AB[i].second;
    }
    sort(AB.begin(), AB.end());
    for(ll i=1;i<=N;i++){
        S[i] = AB[i].second + S[i-1];
    }
    for(ll i=N;i>0;i--){
        MX[i-1] = max(MX[i], S[i] - AB[i].first);
    }
    for(ll i=1;i<=N;i++){
        ans = max(ans, AB[i].first - S[i-1] + MX[i-1]);
    }
    cout<<ans;
}

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