Submission #1033829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033829		nathan4690	Art Exhibition (JOI18_art)	C++17	100 / 100	138 ms	24836 KiB

art

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

ll n,pf[maxn],mx,ans;
pair<ll,ll> pic[maxn];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(ll i=1;i<=n;i++){
        cin >> pic[i].first >> pic[i].second;
    }
    sort(pic+1,pic+n+1);
    for(ll i=1;i<=n;i++){
        pf[i] = pf[i-1] + pic[i].second;
    }
    // Chon doan [i...j]
    //   S[j] - S[i-1] - a[j] + a[i]
    // = (S[j] - a[j]) + (a[i] - S[i-1])
    mx = -inf;
    ans = 0;
    for(ll i=1;i<=n;i++){
        mx = max(mx, pic[i].first - pf[i-1]);
        ans = max(ans, pf[i] - pic[i].first + mx);
    }
    cout << ans;
}

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