Submission #41148

#	Time	Username	Problem	Language	Result	Execution time	Memory
41148		ngkan146	Art Exhibition (JOI18_art)	C++98	100 / 100	253 ms	8664 KiB

art

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll, ll> ii;
int n;
ii a[500005];
int main(){
    iostream::sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a+1,a+n+1);
    ll maxPrefix = 0, ans = (ll) -1e18;
    for(int i=1;i<=n;i++){
        ans = max(ans, a[i].second + maxPrefix);
        maxPrefix = max(0ll, maxPrefix + a[i].second - (a[i+1].first - a[i].first));
    }
    cout << ans;
}

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