Pojemność wody między słupkami

Zadanie 7 z 10 · rozdział 24Trudność: 3 z 3two pointersprefixtrapping rain water

Treść zadania

Otrzymujesz wysokości n słupków stojących obok siebie; każdy słupek ma szerokość 1. Oblicz, ile jednostek wody zatrzyma się pomiędzy słupkami po deszczu (woda spływa poza pierwszy i ostatni słupek).

Nad słupkiem o indeksie i zatrzyma się $\min(L_i, P_i) - h_i$ jednostek wody, gdzie $L_i$ to najwyższy słupek na lewo od i (włącznie z nim), a $P_i$ — najwyższy słupek na prawo od i (włącznie z nim).

Dane wejściowe

1. linia: n — liczba słupków
2. linia: n nieujemnych liczb całkowitych — wysokości słupków

Dane wyjściowe

Jedna liczba całkowita — łączna ilość wody.

Ograniczenia

1 ≤ n ≤ 1000
$0 \le h_i \le 10^4$

Uwagi

Liczenie $L_i$ i $P_i$ od nowa dla każdego słupka daje czas $O(n^2)$. Oczekiwane rozwiązanie działa w czasie $O(n)$: policz maksima prefiksowe i sufiksowe w dwóch przejściach albo użyj dwóch wskaźników idących od końców listy.

Przykład

Wejście

5
3 0 1 0 2

Wyjście

Nad słupkami o indeksach 1, 2 i 3 woda sięga wysokości $\min(3, 2) = 2$, więc zatrzyma się tam odpowiednio $2 + 1 + 2 = 5$ jednostek.

Potrzebujesz teorii?

Listy

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Twój kod w Pythonie

Nie uruchomiono

Wejście

500
98 67 92 29 65 13 80 19 35 97 87 81 91 55 88 78 92 16 41 77 66 3 1 75 40 22 40 29 58 84 61 57 89 55 79 34 73 99 87 62 58 17 18 90 91 40 53 85 36 23 99 9 77 37 59 99 96 5 51 70 53 16 35 50 51 58 58 42 23 62 68 67 68 28 3 92 16 63 73 44 88 43 48 27 6 48 18 54 56 38 73 88 45 63 23 82 3 90 39 46 56 68 3 35 94 79 35 43 84 86 34 22 24 4 18 46 28 10 93 60 5 13 49 37 88 30 42 92 15 94 16 83 66 42 26 9 66 87 32 82 13 47 90 26 23 9 88 99 68 95 1 82 66 71 69 27 22 86 73 6 43 27 57 21 8 1 82 3 57 82 31 66 40 64 15 13 75 21 61 69 18 27 0 73 55 93 25 32 3 24 67 8 7 77 27 74 2 82 46 71 76 25 84 34 14 21 12 44 33 11 58 66 22 48 70 41 33 51 36 24 45 22 55 98 75 97 57 11 45 28 31 59 71 17 92 48 98 63 20 80 68 15 66 54 59 90 35 41 60 56 6 82 3 26 83 16 54 38 98 96 2 60 92 54 72 11 87 5 8 78 38 58 84 35 12 69 64 80 84 42 35 93 99 11 36 42 23 80 2 48 61 13 61 6 27 10 53 44 27 46 9 47 41 96 28 63 91 37 38 44 93 27 63 34 48 31 34 38 83 82 35 42 77 59 15 70 90 11 12 34 25 72 65 97 44 64 52 22 16 6 92 0 29 65 33 69 84 70 96 67 86 50 22 20 77 51 13 70 63 59 72 88 9 39 98 94 72 51 16 48 38 75 54 15 96 77 78 34 17 59 10 49 49 12 33 86 39 78 43 86 53 74 92 49 3 6 88 92 76 57 6 37 24 73 11 57 7 55 9 43 17 83 52 80 33 68 22 86 16 68 81 30 2 63 86 92 68 76 8 36 19 1 39 53 54 87 59 34 82 73 68 90 75 32 69 59 43 2 1 15 85 26 65 81 6 87 96 27 26 80 66 57 17 58 44 2 91 36 63 5 70 75 39 5 17 52 3 83 7 24 81 14 18 5 4 56 27 39 19 84 78 55 73 54 55 72 83 43 44 95

Oczekiwane wyjście

Uruchom z własnymi danymi

Dane wejściowe (to, co program odczyta przez input())