Submission #506135

#	Time	Username	Problem	Language	Result	Execution time	Memory
506135		lucri	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	204 KiB

art

#include <iostream>
#include <algorithm>
using namespace std;
long long s,n,r,ss[500010],sd[500010],r2;
struct tablouri{long long a,b;}t[500010];
bool comp(tablouri a1,tablouri b1)
{
    return a1.a<b1.a;
}
int main()
{
    cin>>n;
    for(long long i=1;i<=n;++i)
    {
        cin>>t[i].a>>t[i].b;
        s+=t[i].b;
    }
    sort(t+1,t+n+1,comp);
    long long j=1,i;
    for(long long i=1;i<=n;++i)
    {
        if(t[i].a==t[j].a)
            t[j].b+=t[i].b;
        else
        {
            ++j;
            t[j]=t[i];
        }
    }
    n=j;
    r=s-t[n].a+t[1].a;
    for(long long i=2;i<=n;++i)
        ss[i]=ss[i-1]-t[i-1].b-t[i-1].a+t[i].a;
    for(long long i=2;i<=n;++i)
        ss[i]=max(ss[i],ss[i-1]);
    for(long long i=n-1;i>=1;--i)
        sd[i]=sd[i+1]-t[i+1].b+t[i+1].a-t[i].a;
    for(long long i=n-1;i>=1;--i)
        sd[i]=max(sd[i],sd[i+1]);
    for(long long i=1;i<=n;++i)
        r2=max(r2,sd[i]+ss[i]);
    cout<<r+r2;
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:19:19: warning: unused variable 'i' [-Wunused-variable]
   19 |     long long j=1,i;
      |                   ^

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