Submission #1117213

#TimeUsernameProblemLanguageResultExecution timeMemory
1117213vjudge1Art Exhibition (JOI18_art)C++17
0 / 100
1 ms336 KiB
#include <bits/stdc++.h> #define F first #define S second #define LL long long #define rep(i, x) for(auto &i : (x)) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define left(x) ((x)<<1) #define right(x) ((x)>>1) #define LSOne(x) (x & -(x)) using namespace std; using T = pair<pair<int, int>, int>; const int SZ = 2e5 + 1; const LL MOD = 1e9 + 7; const LL INF = 1e18 + 1; LL bp (LL b, LL e, LL m = MOD) { if ( e == 0 ) return 1; LL T = bp(b, e / 2); T *= T; T %= m; if ( e & 1 ) T *= b; return T %= m; } LL nv_i (LL a) { return bp(a, MOD - 2); }; LL gcd (LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); } LL lcm(LL a, LL b) { return (a * (b / gcd(a, b))); } LL ceil (LL a, LL b) { return ((a + b - 1) / b); } void solve() { int n; cin >> n; vector<pair<LL, LL>> ARTW(n + 1); vector<LL> AUX(n + 1); for(int i = 1; i <= n; i ++) { cin >> ARTW[i].F >> ARTW[i].S; } sort(all(ARTW)); for(int i = 1; i <= n; i ++) { ARTW[i].S += ARTW[i - 1].S; AUX[i] = ARTW[i].S; } pair<LL, int> mx = {0, 0}; for(int i = 1; i <= n; i ++) { ARTW[i].S -= ARTW[i].F; if(ARTW[i].S >= mx.F) { mx.F = ARTW[i].S; mx.S = i; } } LL ans = 0; for(int i = 1; i <= mx.S; i ++) { LL sum = ARTW[mx.S].S - AUX[i - 1] + ARTW[i].F; ans = max(ans, sum); } for(int i = mx.S + 1; i <= n; i ++) { LL sum = ARTW[i].S - AUX[i - 1] + ARTW[i].F; ans = max(ans, sum); } cout << ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); 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...