Plouă, plouă, plouă…

IT -istul Ghită vă propune următoarea problemă:

Plouă, plouă, plouă…

IT -istul Ghită vă propune următoarea problemă:
pe o platformă sunt montate pe poziții consecutive n bare verticale de lățime 1cm (vezi exemplul). Vom presupune că platforma este mărginită față/spate de ziduri transparente de înălțime infinită. Cantitatea de apă ce poate fi reținută într-o unitate de volum (1cm x 1cm x 1cm) este de 1 mililitru.

Cerința

Determinați cantitatea maximă de apă reținută (exprimată în mililitri).

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, ce reprezintă înălțimile barelor.

Date de ieșire

Programul va afișa pe ecran numărul W, ce reprezintă cantitatea de apă ce poate fi reținută.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• cele n numere citite vor fi mai mici decât 1.000

Exemple:

Intrare

6
3 0 0 2 0 4

Ieșire

10

12
0 1 0 2 1 0 1 3 2 1 2 1

Ieșire

6

Explicație

Pentru primul exemplu:

#include <bits/stdc++.h>

using namespace std;

#define MAX 100001
int n;
int a[MAX], sum;

int c[MAX], s[MAX], indc, inds;

int main()
{
    int bef = 0, sbef = 0;

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    c[++indc] = 1;
    s[++inds] = 0;

    for (int i = 2; i <= n; i++)
    {
        bef = 0;
        sbef = 0;
        while (a[c[indc]] < a[i])
        {
            bef = c[indc];
            sbef = s[inds];
            inds --;
            indc --;
            if (indc == 0)break;
        }

        if (indc == 0)s[++inds] = a[bef] * (i - bef - 1) + sbef, sum += a[bef];
        else s[++inds] = (a[i] * (i - c[indc] - 1));

        c[++indc] = i;
    }

    while (inds)
        sum += s[inds], inds --;

    while (indc)
        sum += a[c[indc]], indc --;

    for (int i = 1; i <= n; i++)
        sum -= a[i];

    cout << sum;
    return 0;
}