Submission #629499

#	Time	Username	Problem	Language	Result	Execution time	Memory
629499		Piokemon	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	132 ms	13192 KiB

bulves

#include <bits/stdc++.h>
using namespace std;

long long int c[500'009];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long int n,a,b,odp = 0;
    cin >> n;
    c[0] = 0;
    for (int x=1;x<=n;x++){
        cin >> a >> b;
        c[x] = a-b;
        //c[x] -= x;
        c[x] += c[x-1];
    }
    priority_queue<int> slope;
    slope.push(0);
    for (int x=1;x<=n;x++){
        if (c[x] < 0){
            odp += 0 - c[x];
            c[x] = 0;
        }
        if (c[x] > c[n]){
            odp += c[x] - c[n];
            c[x] = c[n];
        }
        slope.push(c[x]);
        if (c[x] < slope.top()){
            odp += slope.top() - c[x];
            slope.pop();
            slope.push(c[x]);
        }
    }
    cout << odp << "\n";
    return 0;
}

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