제출 #1269441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269441		k12_khoi	Art Exhibition (JOI18_art)	C++17	100 / 100	125 ms	8264 KiB

art

#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();
}

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