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

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

Ieșire

Explicație

Pentru primul exemplu:

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema water trap:

# include <bits/stdc++.h>
# define NM 100001
using namespace std;

int H[NM], max_left[NM], max_right[NM];
int n;
long long water = 0;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> H[i];

    max_left[0] = H[0];
    for (int i = 1; i < n; i++)
       max_left[i] = max(max_left[i-1], H[i]);

    max_right[n-1] = H[n-1];
    for (int i = n-2; i >= 0; i--)
       max_right[i] = max(max_right[i+1], H[i]);

    for (int i = 0; i < n; i++)
       water += min(max_left[i], max_right[i]) - H[i];

    cout << water << '\n';

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2084 water trap

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2084 water trap de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2084 water trap