Submission #213070

#	Time	Username	Problem	Language	Result	Execution time	Memory
213070		qkxwsm	Potatoes and fertilizers (LMIO19_bulves)	C++14	24 / 100	136 ms	21096 KiB

bulves

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 500013;
const int INF = 1000000007;

int N;
ll arr[MAXN];
ll net[MAXN];
ll ans;
vpl lt, rt;

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    FOR(i, 0, N)
    {
        int a, b;
        cin >> a >> b;
        arr[i] = a - b;
        // cerr << arr[i] << '\n';
    }
    lt.PB({INF, -INF});
    rt.PB({INF, INF});
    FORD(i, N, 0)
    {
        if (arr[i] > 0) rt.PB({arr[i], i});
    }
    FOR(i, 0, N)
    {
        if (rt.back().se == i)
        {
            lt.PB(rt.back());
            rt.pop_back();
        }
        while(arr[i] < 0)
        {
            ll dl = i - lt.back().se, dr = rt.back().se - i;
            // cerr << dl << ' ' << dr << endl;
            if (dl < dr)
            {
                ll c = lt.back().fi;
                ll gain = min(c, -arr[i]);
                c -= gain;
                arr[i] += gain;
                // cerr << "wtf " << lt.back().se << endl;
                net[lt.back().se] += gain;
                net[i] -= gain;
                // cerr << dl << ' ' << gain << endl;
                lt.back().fi = c;
                if (lt.back().fi == 0) lt.pop_back();
            }
            else
            {
                ll c = rt.back().fi;
                ll gain = min(c, -arr[i]);
                c -= gain;
                arr[i] += gain;
                net[i] -= gain;
                // cerr << "wtf " << rt.back().se << endl;
                net[rt.back().se] += gain;
                // cerr << dr << ' ' << gain << endl;
                rt.back().fi = c;
                if (rt.back().fi == 0) rt.pop_back();
            }
        }
    }
    FOR(i, 1, N)
    {
        net[i] += net[i - 1];
    }
    FOR(i, 0, N)
    {
        ans += abs(net[i]);
    }
    cout << ans << '\n';
    return 0;
    //make all arr's positive, what's the cost?

}

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