Submission #1202838

#TimeUsernameProblemLanguageResultExecution timeMemory
1202838andrejikusArt Exhibition (JOI18_art)C++20
100 / 100
119 ms23912 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) const int N = 5e5 + 3; ll a[N], b[N], U[N], pref[N]; void solve() { int n; cin >> n; vector<pair<ll, ll>> vec; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], vec.push_back({a[i], b[i]}); sort(vec.begin(), vec.end()); ll ans = 0; for (int i = 1; i < n; i++) { U[i] = vec[i-1].second - (vec[i].first - vec[i-1].first); pref[i] = pref[i-1] + U[i]; } ll mn = 0; for (int i = 1; i <= n; i++) { ll S = vec[i-1].second; //dbg(S, pref[i-1], mn, i); ans = max(ans, S + pref[i-1] - mn); mn = min(mn, pref[i]); } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; //cin >> t; while (t--) { solve(); } } /* 3 2 3 4 5 11 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...