Submission #1269441

#TimeUsernameProblemLanguageResultExecution timeMemory
1269441k12_khoiArt Exhibition (JOI18_art)C++17
100 / 100
125 ms8264 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,int>
#define X first
#define Y second

const int N=5e5+5;

int n; ll res;
pii a[N];

namespace sub1
{
    void ql(int i,ll mi,ll ma,ll sum)
    {
        if (i>n)
        {
            res=max(res,sum-(ma-mi));
            return;
        }

        ql(i+1,mi,ma,sum);

        ql(i+1,min(mi,a[i].X),max(ma,a[i].X),sum+a[i].Y);
    }

    void solve()
    {
        res=0;
        for (int i=1;i<=n;i++)
        ql(i+1,a[i].X,a[i].X,a[i].Y);

        cout << res;
    }
}

namespace sub2
{
    ll temp,ma,res;

    void solve()
    {
        sort(a+1,a+n+1);

        ma=a[1].Y+a[1].X;
        res=a[1].Y;

        for (int i=2;i<=n;i++)
        {
            temp=ma-a[i].X+a[i].Y;

            if (temp<a[i].Y) temp=a[i].Y;

            res=max(res,temp);

            ma=max(ma,temp+a[i].X);
        }

        cout << res;
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i=1;i<=n;i++)
    cin >> a[i].X >> a[i].Y;

    sub2::solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...