Submission #1153791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153791		simuyu	Po (COCI21_po)	C++20	10 / 70	6 ms	1608 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long

ll N;
ll diffs[100005];

ll res;

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

    // get difference array
    cin >> N;
    ll prev, t;
    prev = 0;
    for (ll i=0; i<N; i++) {
        cin >> t;
        diffs[i] = t-prev;
        prev = t;
    }
    diffs[N] = 0-prev;

    // greedy
    res = 0;
    stack<ll> holds;
    for (ll i=0; i<=N; i++) {
        // loop through difference array
        if (diffs[i] == 0) continue; // nothing to do

        if (diffs[i] > 0) { // if adding
            holds.push(diffs[i]);
            continue;
        }

        // otherwise it's subtracting
        t = -diffs[i]; // amount to be subtracted
        while (t>0) {
            if (t >= holds.top()) {
                t -= holds.top();
                holds.pop();
                res++;
            } else { // t < holds.top(), so we kind of decrease the top a little only.
                t = holds.top() - t;
                holds.pop();
                holds.push(t);
                break;
            }
        }

    }

    cout << res << endl;


    return 0;
}

• Subtask 1: 10 / 70