Submission #477952

#	Time	Username	Problem	Language	Result	Execution time	Memory
477952		Mihai_Eduard	Art Exhibition (JOI18_art)	C++14	100 / 100	592 ms	32568 KiB

art

#include <bits/stdc++.h>

#define NMAX 500005
typedef long long ll;

using namespace std;

int N;
ll sum[NMAX], minim[NMAX], maxim[NMAX], sol=-1;
struct artwork
{
    ll sz, val;
}v[NMAX];

bool comp(artwork A, artwork B)
{
    return A.sz<B.sz;
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
        cin>>v[i].sz>>v[i].val;

    sort(v+1,v+N+1,comp);

    for(int i=1;i<=N;i++)
        sum[i]=sum[i-1]+v[i].val;

    minim[1]=sum[0]-v[1].sz;
    for(int i=2;i<=N;i++)
        minim[i]=min(minim[i-1],sum[i-1]-v[i].sz);
    maxim[1]=sum[1]-v[1].sz;
    sol=maxim[1]-minim[1];
    for(int i=2;i<=N;i++)
    {
        maxim[i]=sum[i]-v[i].sz;
        sol=max(sol,maxim[i]-minim[i]);
    }
    cout<<sol;
}

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