Tècniques d'entrenament (1) P52820

Statement

thehtml

En els entrenaments de programació de la UPC hi ha xocolatines, coques, panellets, torrons, magdalenes... Per què calen? Quan un estudiant intenta resoldre un problema, la seva autoestima puja o baixa en funció de si ho aconsegueix. Si l’autoestima baixa per sota d’un llindar de resistència mental −R, l’estudiant deixa d’entrenar i se’n va plorant. Per evitar-ho, el professor Oak la pot pujar tant com vulgui repartint galetes (cada galeta suma un). Curiosament, a vegades es produeix el fenomen oposat: alguns estudiants amb massa autoestima (per sobre de R), es creuen molt bons i deixen d’entrenar. Per evitar aquests casos, unes quantes fuetejades fan baixar l’autoestima (cada cop de fuet resta un).

Coneixent quin increment d’autoestima provocarà cada problema en un estudiant fixat, quina és la mínima resistència mental R que cal que tingui perquè no marxi de l’entrenament, si s’escull de forma òptima la quantitat de galetes o de cops de fuet que cal donar-li abans de resoldre cada problema?

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de problemes n, seguit, en l’ordre que s’intentaran resoldre els problemes, dels n increments x_i d’autoestima que provoquen cadascun. Suposeu 1 ≤ n ≤ 10⁴, i que els x_i són enters entre −10⁴ i 10⁴.

Sortida

Per a cada cas, escriviu la mínima resistència mental R que ha de tenir l’estudiant. Suposeu que la seva autoestima inicial és zero.

Public test cases

Input

3  0 0 0
1 -6
1  5
2  1 -2
2  -2 1
4  1 1 1 1
3  20 -70 -40

Output

Information

Author: Maria Bauzà i Ferran Alet
Language: Catalan
Official solutions: C++
User solutions: C++