Submission #1109221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109221		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	182 ms	16096 KiB

art

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
const int N = 5e5+5 ;
const int M = 1e7+5; 
const int mod = 1e9+7;
pair<int,int> a[N] ;
int sufmax[N] ;
int ps[N] ;
signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    int n ;
    cin >> n ;
    for (int i = 1 ; i<= n ;i++) {
        cin >> a[i].first >> a[i].second ;
    }
    sort(a+1, a+1+n); 
    for (int i = 1; i<= n ;i++) {
        ps[i] = ps[i-1] + a[i].second ;
    }
    sufmax[n+1] = -1e18 ;
    for (int i = n ;i >= 1 ;i--) {
        sufmax[i] = max(sufmax[i+1] , ps[i] - a[i].first) ;
    }
    int mn = LLONG_MAX ;
    int res= 0 ; 
    for (int i = 0 ; i < n ;i++) {
        mn = min(mn ,ps[i] - a[i+1].first) ;
        //cout << mn << " " << sufmax[i+1] << endl ;
        res = max(res, sufmax[i+1] - mn) ;
    }
    cout << res ;
}

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