Submission #233809

#	Time	Username	Problem	Language	Result	Execution time	Memory
233809		Nodir_Bobiev	Art Exhibition (JOI18_art)	C++14	100 / 100	330 ms	36604 KiB

art

/*
+----------------------------------------------------------------+
| In the name of Allah, the most Gracious and the most Merciful. |
+----------------------------------------------------------------+
Creator of the earth and sky
We ask for a rank that is high
We obey in word and deed
The prophet’s we must heed.

And when your scars are hurting
And your heart is in fear
Remember just remember
Allah is really here.
*/
# include <bits/stdc++.h>
# define FILE
using namespace std;

const int N = 5e5 + 100;
int n;
long long A[N], B[N], C[N], sum[N], S[N], mx[N], ans=-1e18;

bool cmp( int a, int b ){
    return A[a] <= A[b];
}

int main(){
    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio(false);
    cin >> n;
    for( int i = 1; i <= n; i ++ ){
        cin >> A[i] >> B[i];
        C[i] = i;
    }
    sort( C+1, C+n+1, cmp );
    sort( A+1, A+n+1 );
    for( int i = 1; i <= n; i ++ ){
        sum[i] += sum[i-1] + B[C[i]];
        S[i] = sum[i] - A[i];
    }
    mx[n] = S[n];
    for( int i = n-1; i >= 1; i -- ){
        mx[i] = max(mx[i+1], S[i]);
    }
    for( int i = 1; i <= n; i ++ ){
        ans = max( ans, mx[i]-sum[i-1]+A[i] );
    }
    cout << ans;
}

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