Submission #146925

#	Time	Username	Problem	Language	Result	Execution time	Memory
146925		willi19	Art Exhibition (JOI18_art)	C++14	0 / 100	2 ms	376 KiB

art

#include <bits/stdc++.h>
using namespace std;
int n;
long long maxt[2000100],ans,val[500100];
pair<long long,long long> pic[500100];
void init(int s,int f,int node)
{
    if(s==f)
    {
        maxt[node]=val[s];
        return;
    }
    init(s,(s+f)/2,node*2);
    init((s+f)/2+1,f,node*2+1);
    maxt[node]=max(maxt[node*2],maxt[node*2+1]);
}
long long query(int s,int f,int node,int l,int r)
{
    if(f<l||r<s)
        return -100000000000000000;
    if(l<=s&&f<=r)
        return maxt[node];
    return max(query(s,(s+f)/2,node*2,l,r),query((s+f)/2+1,f,node*2+1,l,r));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>pic[i].first>>pic[i].second;
    sort(pic+1,pic+n+1);
    for(int i=1;i<=n;i++)
        val[i]+=(val[i-1]+pic[i-1].first-pic[i].first+pic[i].second);
    init(1,n,1);
    ans=-100000000000000000;
    for(int i=1;i<n;i++)
        ans=max(ans,query(1,n,1,i+1,n)-val[i]+pic[i].second);
    cout<<ans;
}

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