Submission #531116

#	Time	Username	Problem	Language	Result	Execution time	Memory
531116		Vladth11	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	376 ms	15276 KiB

bulves

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 500001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll nr_of_bits = 21;

int n;
ll v[NMAX], a, b;

int main() {
    //ifstream cin("niceset.in");
    //ofstream cout("niceset.out");
    int i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> a >> b;
        a -= b;
        v[i] = a;
        v[i] += v[i - 1];
    }
    ll sol = 0;
    priority_queue <ll> pq;
    for(i = 1; i <= n; i++){
        if(v[i] < 0){
            sol += -v[i];
            v[i] = 0;
        }
        if(v[i] > v[n]){
            sol += (v[i] - v[n]);
            v[i] = v[n];
        }
        pq.push(v[i]);
        pq.push(v[i]);
        sol += (v[n] - v[i]);
        sol -= (v[n] - pq.top());
        pq.pop();
    }
    cout << sol;
    return 0;
}

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