oj.uz

Submission #213070

# Submission time Handle Problem Language Result Execution time Memory
213070 2020-03-24T23:45:08 Z qkxwsm Potatoes and fertilizers (LMIO19_bulves) C++14
24 / 100
 136 ms 21096 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 15 ms 2044 KB Output is correct
5 Correct 23 ms 3568 KB Output is correct
6 Correct 65 ms 8564 KB Output is correct
7 Correct 136 ms 19048 KB Output is correct
8 Correct 119 ms 21096 KB Output is correct
9 Correct 105 ms 16492 KB Output is correct
10 Correct 81 ms 14184 KB Output is correct
11 Correct 85 ms 14184 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 15 ms 2044 KB Output is correct
5 Correct 23 ms 3568 KB Output is correct
6 Correct 65 ms 8564 KB Output is correct
7 Correct 136 ms 19048 KB Output is correct
8 Correct 119 ms 21096 KB Output is correct
9 Correct 105 ms 16492 KB Output is correct
10 Correct 81 ms 14184 KB Output is correct
11 Correct 85 ms 14184 KB Output is correct
12 Incorrect 38 ms 4968 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Incorrect 5 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Incorrect 5 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -