Submission #362437

#	Time	Username	Problem	Language	Result	Execution time	Memory
362437		Yeboi	Art Exhibition (JOI18_art)	C++14	100 / 100	636 ms	44728 KiB

art

#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(long long i(a); i<b ; i++)
#define inf -pow(10,9)
#define MAXN 100000 
const ll INF = 1000000000;
const ll N = 50005;
const ll modi = 1000000007;
const ll modi2= 1000000006;
using namespace std;

int main(){
        ll n;
        cin >> n;
        ll a[n+1];
        ll b[n+1];
        vector<pair<ll,ll>> v;
        rep(i,n){
            cin >> a[i] >> b[i];
            v.push_back(make_pair(a[i],b[i]));
        }
        sort(v.begin(),v.end());
        rep(i,n){
            a[i]=v[i].first;
            b[i]=v[i].second;
        }
        ll pre[n+1]={0};
        pre[0]=b[0];
        f(i,1,n){
            pre[i]=pre[i-1]+b[i];
        }
        ll p1[n+1];
        ll p2[n+1];
        rep(i,n){
            p1[i]=pre[i]-a[i];
            if(i==0){
                continue;
            }
            p2[i]=pre[i-1]-a[i];
        }
        ll curr[n+1];
        curr[0]=1e18;
        f(i,1,n){   
            curr[i]=min(curr[i-1],p2[i]);
        }
        ll ans=b[0]-a[0];
        f(i,1,n){
            ans=max(ans,p1[i]-curr[i]);
            ans=max(ans,p1[i]+a[0]);
        }   
        cout << ans << endl;
}

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