Submission #200330

#	Time	Username	Problem	Language	Result	Execution time	Memory
200330		blue	Art Exhibition (JOI18_art)	C++17	100 / 100	917 ms	32760 KiB

art

#include <iostream>
#include <algorithm>
using namespace std;

long long* X;
long long* Y;

bool f(long long a, long long b)
{
    return X[a] < X[b];
}

int main()
{
    long long N;
    cin >> N;
    X = new long long[N+1];
    Y = new long long[N+1];
    long long A[N+1], B[N+1];
    for(long long i = 1; i <= N; i++) cin >> X[i] >> Y[i];

    long long I[N+1];
    for(long long i = 0; i <= N; i++) I[i] = i;
    sort(I+1, I+N+1, f);

    long long a = 1;
    for(long long i:I)
    {
        if(i == 0) continue;
        A[a] = X[i];
        B[a] = Y[i];
        a++;
    }
    for(long long i = 2; i <= N; i++) B[i] += B[i-1];

    A[0] = B[0] = 0;

    for(long long i = 1; i <= N; i++)
    {
        X[i] = A[i] - B[i-1];
        Y[i] = B[i] - A[i];
    }

    for(long long i = N-1; i >= 1; i--) Y[i] = max(Y[i], Y[i+1]);

    long long res = 0;
    for(long long i = 1; i <= N; i++) res = max(res, X[i] + Y[i]);

    cout << res << '\n';
    return 0;
}

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