제출 #233809

#제출 시각아이디문제언어결과실행 시간메모리
233809Nodir_BobievArt Exhibition (JOI18_art)C++14
100 / 100
330 ms36604 KiB
/*
+----------------------------------------------------------------+
| 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;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...