Editing 2033 - MCub

Alexandru este foarte pasionat de cuburi. Într-o zi, acesta a creat un zid format din <code>N</code> turnuri de cuburi, turnul <code>i</code> fiind alcătuit din <code>H[i]</code> cuburi puse unul peste altul. Având acest zid, el își pune următoarea întrebare: Dacă aș porni de la un zid “gol” cu <code>N</code> turnuri (gol înseamnă ca <code>H[i] = 0</code> pentru orice <code>1 ≤ i ≤ N</code>) iar singura operație pe care o pot face este să aleg doi indici <code>i</code> și <code>j</code> cu <code>1 ≤ i ≤ j ≤ N</code> și să pun câte un cub peste fiecare turn în intervalul <code>i</code> și <code>j</code>, care este numărul minim de astfel de operații ce trebuie efectuate pentru a obține zidul inițial?

= Cerința =
Lui Alexandru i s-a părut banală problema așa că te provoacă și pe tine să o rezolvi.

= Date de intrare =
Fișierul de intrare <code>mcub.in</code> conține pe prima linie numărul <code>N</code>, iar pe a doua linie <code>N</code> numere naturale ce reprezintă înălțimile fiecărui turn al zidului.

= Date de ieșire =
Fișierul de ieșire <code>mcub.out</code> va conține pe prima linie numărul <code>S</code>, reprezentând răspunsul întrebării puse de Alex.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât <code>1.000.000</code>

= Exemplu: =
<code>mcub.in</code>
 5
 1 0 3 1 2
<code>mcub.out</code>
 5

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python">
import sys

sys.stdintxt = open('mcubin.txt', 'r')

sys.stdouttxt = open('mcubout.txt', 'w')

n = int(input())

hmax = 0

rez = 0

for i in range(1, n+1):

    hmax = h

    h = int(input())

    if h > hmax:

        rez += h - hmax

print(rez)

</syntaxhighlight>