# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
713643 | 2023-03-22T17:57:23 Z | EqualTurtle | Potatoes and fertilizers (LMIO19_bulves) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; constexpr int MAXN = 5e5 + 7; long long tab[MAXN]; int n; long long res; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; priority_queue<long long> pq; for (int i = 1; i <= n; i++) { long long a; cin >> tab[i] >> a; tab[i] += tab[i - 1] - a; } for (int i = 1; i <= n; i++) { // modyfikacja zeby wartosci byly z przedzialu (0, #nawozow - #ziemniakow) if (tab[i] < 0) { res -= tab[i]; tab[i] = 0; } else if (tab[i] > tab[nums]) { res += tab[i] - tab[nums]; tab[i] = tab[nums]; } // a dalej klasyczna sztuczka pq.push(tab[i]); pq.push(tab[i]); res += pq.top() - tab[i]; pq.pop(); } cout << res << "\n"; return 0; }