Submission #713341

#	Time	Username	Problem	Language	Result	Execution time	Memory
713341		_martynas	Potatoes and fertilizers (LMIO19_bulves)	C++11	100 / 100	225 ms	19164 KiB

bulves

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 5e5+5;

int n;
ll A[MXN], B[MXN];

int main() {
    FASTIO();
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> A[i] >> B[i], A[i] -= B[i], A[i] += A[i-1];
    priority_queue<ll> PQ;
    ll sy = 0;
    for(int i = 1; i < n; i++) {
        if(A[i] < 0) sy += -A[i], A[i] = 0;
        sy += A[i];
        PQ.push(A[i]);
        PQ.push(A[i]);
        PQ.pop();
    }
    ll ans = sy;
    while(!PQ.empty()) {
        ans -= min(A[n], PQ.top());
        PQ.pop();
    }
    cout << ans << "\n";
    return 0;
}

/*



*/

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