Submission #920974

#	Time	Username	Problem	Language	Result	Execution time	Memory
920974		vjudge1	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	105 ms	7268 KiB

bulves

#include <iostream>
#include <queue>

using namespace std;
#define N 500005

int n, a[N], b[N];
priority_queue<pair<int, int>> pq, qq;
long long cost;

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int a, b;
        cin >> a >> b;
        pq.emplace(i, a);
        while (b and pq.size())
        {
            auto [j, aa] = pq.top(); pq.pop();
            auto u = min(b, aa);
            cost += 1ll*u*(i-j);
            b -= u;
            if (aa > u) pq.emplace(j, aa - u);
        }
        if (b)
        {
            qq.emplace(i, b);
        }
        while (pq.size() and qq.size())
        {
            auto [j, aa] = pq.top(); pq.pop();
            auto [k, bb] = qq.top(); qq.pop();
            auto u = min(aa, bb);
            cost += 1ll*abs(j-k)*u;
            if (aa > u) pq.emplace(j, aa - u);
            if (bb > u) qq.emplace(k, bb - u);
        }
    }
    cout<<cost;
    return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36