Submission #1202998

#TimeUsernameProblemLanguageResultExecution timeMemory
1202998NeltPotatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
143 ms8380 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; void solve() { ll n; cin >> n; ll a[n]; { ll sum = 0; for (ll i = 0; i < n; i++) { ll x, y; cin >> x >> y; sum += x - y; a[i] = sum; } } ll ans = 0; priority_queue<ll> q; for (ll i = 0; i < n - 1; i++) { if (a[i] < 0) ans -= a[i], a[i] = 0; ans += a[i]; q.push(a[i]); q.push(a[i]); q.pop(); } while (!q.empty()) { ans -= min(q.top(), a[n - 1]); q.pop(); } cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...