Submission #591726

#	Time	Username	Problem	Language	Result	Execution time	Memory
591726		piOOE	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	138 ms	15232 KiB

bulves

#include <bits/stdc++.h>
 
using namespace std;
 
 
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;
 
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
#define ll long long
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) -  begin(x))
#define ld long double
#define sz(s) (int) size(s)
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define mt make_tuple
#define int128 __int128
 
 
template<typename T>
bool ckmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
 
template<typename T>
bool ckmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
 
int bit(int x, int b) {
    return (x >> b) & 1;
}
 
 
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
 
const ll infL = 3e18;
const int infI = 1e9 + 7;
const int N = 500001;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
 
ll A[N];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        A[i] = (i ? A[i - 1] : 0) + a - b;
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] < 0) {
            //it means that on our prefix sum(b) > sum(a) so we have to take some a's from right and put them here
            ans += -A[i];
            A[i] = 0;
        }
        if (A[i] > A[n - 1]) {
            //it means that now we have to take some from here and put them righter
            ans += A[i] - A[n - 1];
            A[i] = A[n - 1];
        }
    }
    //now everything on every prefix is alright so let's go to solve classic problem about making this array non-decreasing
    priority_queue<ll> pq;
    for (int i = 0; i < n; ++i) {
        pq.push(A[i]);
        pq.push(A[i]);
        ans += pq.top() - A[i];
        pq.pop();
    }
    cout << ans;
    return 0;
}

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