Submission #251865

#	Time	Username	Problem	Language	Result	Execution time	Memory
251865		abacaba	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	200 ms	30948 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

#define int long long

const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 1e6 + 15;
int n, a[N], b[N], diff[N], d[N];
priority_queue <int> q;
int ans;
int opt[N];

signed main() {
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    // setin("input.txt");
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i];
    for(int i = 1; i <= n; ++i)
        diff[i] = a[i] - b[i];
    for(int i = 1; i <= n; ++i)
        d[i] = d[i-1] + diff[i];
    for(int i = 1; i <= n; ++i) {
        if(d[i] < 0)
            ans += abs(d[i]);
        Max(d[i], 0LL);
    }
    for(int i = 1; i <= n; ++i) {
        q.push(d[i]);
        q.push(d[i]);
        opt[i] = q.top();
        q.pop();
    }
    opt[n] = d[n];
    for(int i = n - 1; i; --i) {
        Min(opt[i], opt[i + 1]);
        ans += abs(opt[i] - d[i]);
    }
    cout << ans << endl;
    return 0;
}

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