# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1101791 | 2024-10-16T19:36:14 Z | kasdo | Art Exhibition (JOI18_art) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define speed cin.tie (0) -> sync_with_stdio (0);ios_base::sync_with_stdio(false);cin.tie(0); void solve() { int n; cin>>n; pair<int, int> a[n + 5]; for(int i=1; i<=n; i++) cin>>a[i].first>>a[i].second; sort(a+1, a+n+1); int s[n + 5] = {}, mx[n + 5] = {}, p[n + 5] = {}, mx[n+1] = -1000000000000000000; for(int i=1; i<=n; i++) { p[i] = p[i - 1] + a[i].second; s[i] = p[i] - a[i].first; } for(int i=n; i>=1; i--) mx[i] = max(mx[i + 1], s[i]); int ans = 0; for(int i=1; i<=n; i++) { int cur = -1000000000000000000; // for(int j=i; j<=n; j++) cur = max(cur, (p[j] - a[j].first)); // ai = mn, aj = mx; ans = max(ans, mx[i] - (p[i - 1] - a[i].first)); // ans = max(ans, cur - (p[i - 1] - a[i].first)); } cout<<ans<<endl; } signed main () { speed // freopen("feast.in", "r", stdin); // freopen("feast.out", "w", stdout); int _ = 1; // cin>>_; while(_--) solve(); return 0; }