Submission #1109221

#TimeUsernameProblemLanguageResultExecution timeMemory
1109221vjudge1Art Exhibition (JOI18_art)C++17
100 / 100
182 ms16096 KiB
#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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...