Submission #988813

#TimeUsernameProblemLanguageResultExecution timeMemory
988813MuhammetArt Exhibition (JOI18_art)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define N 500005 #define ll long long int #define sz(x) (int)x.size() #define ff first #define ss second ll T, n, b[N], mx[N]; pair <ll,ll> a[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; ll s = 0; for(int i = 1; i <= n; i++){ cin >> a[i].ff >> a[i].ss; s += a[i].ss; } sort(a+1,a+n+1); ll ans = (s - (a[n].ff - a[1].ff)); for(int i = n; i >= 1; i--){ b[i] = b[i+1]; b[i] -= a[i].ss; b[i] += (a[i].ff - a[i-1].ff); mx[i] = max(mx[i+1], b[i]); } ll x = 0, k = max(0ll,mx[1]); for(int i = 1; i <= n; i++){ x -= a[i].ss; x += (a[i+1].ff - a[i].ff); k = max(k,x + mx[i+1]); } ans += k; cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...