Submission #1248276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248276		Chris_Black	Potatoes and fertilizers (LMIO19_bulves)	C++20	100 / 100	103 ms	16428 KiB

bulves

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pii pair<int, int>
#define ff first
#define ss second
#define pll pair<ll, ll>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vpl vector<pll>
#define vvpl vector<vpl>
#define vl vector<ll>
#define vvl vector<vl>
//#define x first
//#define y second


using namespace std;
const int N = 1e6 + 9, LGV = 33, LGN = 21, Mod = 1e9 + 7;
const int Inf = 0x3f3f3f3f;
//const ll Inf = LLONG_MAX / 2;
const bool test_case = false;

//ifstream fin("input.txt");
//ofstream fout("output.txt");
//#define cin fin
//#define cout fout

ll n, a[N], b[N], d[N];

void solve()
{
    cin >> n;
    FOR(i, 1, n)cin >> a[i] >> b[i];

    FOR(i, 1, n)d[i] = a[i] - b[i];
    FOR(i, 1, n)d[i] += d[i - 1];

    ll ans = 0;

    ///make sure that there is no 0
    FOR(i, 1, n)
        if(d[i] < 0)
            ans -= d[i], d[i] = 0;

    ///make sure that no element surpasses last element
    FOR(i, 1, n - 1)
        if(d[i] > d[n])
            ans += d[i] - d[n], d[i] = d[n];

    priority_queue<ll> q;
    FOR(i, 1, n - 1)
    {
        q.push(d[i]);
        q.push(d[i]);

        ans += q.top() - d[i];
        q.pop();
    }

    while(!q.empty() && q.top() > d[n])
    {
        ans += q.top() - d[n];
        q.pop();
    }

    ///d[i] must be strictly increasing (i.e) no

    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    if(test_case)cin >> t;
    while(t --)solve();
    return 0;
}

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