# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
713643 | EqualTurtle | Potatoes and fertilizers (LMIO19_bulves) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}