Submission #889242

#	Time	Username	Problem	Language	Result	Execution time	Memory
889242		alexander707070	Art Exhibition (JOI18_art)	C++14	100 / 100	171 ms	21076 KiB

art

#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

const long long inf=1e18;

struct pic{
    long long sz,cost;
};

int n;
pic c[MAXN];
long long ans;

bool cmp(pic fr,pic sc){
    return fr.sz<sc.sz;
}

void solve(int l,int r){
    if(l>r)return;
    if(l==r){
        ans=max(ans,c[l].cost);
        return;
    }

    int mid=(l+r)/2;

    long long maxpref=0,maxsuff=0,sum;

    sum=0;
    for(int i=mid;i>=l;i--){
        sum+=c[i].cost;
        maxpref=max(maxpref,sum-(c[mid].sz-c[i].sz));
    }

    sum=0;
    for(int i=mid+1;i<=r;i++){
        sum+=c[i].cost;
        maxsuff=max(maxsuff,sum-(c[i].sz-c[mid+1].sz));
    }

    ans=max(ans,maxpref+maxsuff-(c[mid+1].sz-c[mid].sz));

    solve(l,mid);
    solve(mid+1,r);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i].sz>>c[i].cost;
    }

    sort(c+1,c+n+1,cmp);

    solve(1,n);

    cout<<ans<<"\n";

    return 0;
}

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