waterfill.cpp

#include <iostream>

using namespace std;

int main(){

    int n;
    cin >> n;
    int *ar = new int[n];

    for (int i = 0; i < n; i++)
        cin >> ar[i];

    int ileft = 0, iright = 0, left, right, tmph, total = 0, imax;

    while (ileft < n){
        tmph = -1;
        while (ileft < n - 1 && ar[ileft + 1] >= ar[ileft])
            ileft++;
        if (ileft >= n - 1)
            break;
        iright = ileft;
        while (iright < n && ar[ileft] > ar[++iright]){
            if (ar[iright] >= tmph){
                tmph = ar[iright];
                imax = iright;
            }
        };
        if (iright < n && ar[iright] >= ar[ileft]){
            for (int i = ileft; i < iright; i++){
                total += ar[ileft] - ar[i];
            }
            ileft = iright;
            continue;
        }
        if (iright >= n){
            ar[ileft] = tmph;
        }
        for (int i = ileft; i < imax; i++){
            total += ar[ileft] - ar[i];
        }
        ileft = imax;
    }

    cout << total << endl;

    delete [] ar;

    return 0;
}