Submission #122748

#	Time	Username	Problem	Language	Result	Execution time	Memory
122748		arnold518	Art Exhibition (JOI18_art)	C++14	100 / 100	274 ms	26848 KiB

art

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

struct Art
{
    ll a, b, d;
};

int n;
Art arr[MAXN+10];
ll ans;

int main()
{
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%lld%lld", &arr[i].a, &arr[i].b);

    sort(arr+1, arr+n+1, [&](Art p, Art q) { return p.a<q.a; });
    for(i=1; i<=n; i++) arr[i].b+=arr[i-1].b, arr[i].d=arr[i].b-arr[i].a;

    vector<int> S;
    for(i=n; i>=1; i--)
    {
        if(S.empty() || arr[S.back()].d<arr[i].d) S.push_back(i);
    }

    for(i=1; i<=n; i++)
    {
        ans=max(ans, arr[i].a+arr[S.back()].d-arr[i-1].b);
        if(S.back()==i) S.pop_back();
    }
    printf("%lld", ans);
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:21:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
art.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
art.cpp:24:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=n; i++) scanf("%lld%lld", &arr[i].a, &arr[i].b);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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