Submission #546130

#	Time	Username	Problem	Language	Result	Execution time	Memory
546130		gimabd30	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	108 ms	15212 KiB

bulves

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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]);
        pq.pop();
        ans += pq.top() - A[i];
    }
    cout << ans;
    return 0;
}

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