3262 - Rain

Bariere impermeabile de înălțimi diferite sunt plasate perpendicular pe lungimea unei cuve dreptunghiulare. Distanța dintre oricare două bariere alăturate este de un centimetru. Cuva nu are capac și atunci când plouă destul, cuva este umplută cu apă. Unele bariere pot fi înălțate cu o valoare întreagă care nu poate depăși o valoare dată.

Cerința

Care este numărul minim de bariere care trebuie înălțate astfel încât să fie colectată în cuvă o cantitate maximă de apă?

Date de intrare

Programul citește de pe prima linie numărul n de bariere. A doua linie conține înălțimile celor n bariere, luate de la stânga la dreapta. A treia linie conține numărul k de bariere cărora li se poate crește înălțimea. Urmează atâtea linii câte bariere sunt cărora le putem crește înălțimea. Fiecare din aceste linii conține numărul barierei și creșterea maximă în centimetri în înălțime care se poate face. Numerotarea barierelor se face începând cu 0.

Date de ieșire

Programul va afișa pe ecran doi întregi separați prin spațiu, numărul minim de bariere cărora li se va mări înălțimea și cantitatea maximă de apă ce poate fi colectată după mărire.

Observație: Se calculează cantitatea în centimetri cubi deoarece considerăm adâncimea cuvei de un centimetru. Considerăm fața și spatele pereți ai cuvei (cea care este înspre noi și cea care este în spate) ca fiind mai înalte decât înălțimea oricărei bariere. Pereții din stânga și din dreapta ai cuvei coincid cu cea mai din stânga și respectiv cea mai din dreapta barieră, chiar și după ce acestea vor fi eventual înălțate.

Restricții și precizări

• 1 < n < 1.000.000
• 0 < k ≤ n
• înălțimile inițiale ale celor n bariere sunt numere naturale mai mici sau egale cu 1.000.000
• barierele vor fi înălțate cu maximum 1.000.000

Exemplu:

Intrare

6
2 4 2 4 2 1
2
2 1
4 1

Ieșire

1 14

Explicație

Nu se crește înălțimea barierei 2 deoarece nu va modifica întreaga cantitate de apă. Vom crește cu 1 centimetru înălțimea barierei de la poziția 4, care va mări cantitatea totală de apă cu 1 centimetru cub.

Rezolvare

<syntaxhighlight lang="python3"> nMax = 1000000 H = [0] * nMax max_dH = [0] * nMax LR = [] RL = [] n = 0 dn = 0 KL = 0 KR = 0 countB = 0 volume = 0 L = -1 R = -1

def input_data():

   global n, H, dn, max_dH
   n = int(input())
   H[:n] = map(int, input().split())
   dn = int(input())
   for _ in range(dn):
       j, dH = map(int, input().split())
       max_dH[j] = dH
       H[j] += dH

def scan():

   global KL, KR, L, R
   KL = 0
   for i in range(1, n):
       if H[KL] < H[i]:
           L = KL
           LR.append(KL)
           KL = i
   KR = n - 1
   for i in range(n - 2, KL - 1, -1):
       if H[KR] < H[i]:
           R = KR
           RL.append(KR)
           KR = i

def solve():

   global countB, volume, L, R
   if LR:
       LR.append(KL)
       for i in range(len(LR) - 1):
           if max_dH[LR[i]] > 0:
               countB += 1
           volume += H[LR[i]] * (LR[i + 1] - LR[i])
   if RL:
       RL.append(KR)
       for i in range(len(RL) - 1):
           if max_dH[RL[i]] > 0:
               countB += 1
           volume += H[RL[i]] * (RL[i] - RL[i + 1])
   if KL < KR:
       if max_dH[KL] > 0:
           countB += 1
       if max_dH[KR] > 0:
           countB += 1
       volume += H[KL] * (KR - KL)
   else:
       HLmax = H[L] if L != -1 else 0
       HRmax = H[R] if R != -1 else 0
       if HLmax != HRmax:
           if H[KL] - max_dH[KL] < max(HRmax, HLmax):
               countB += 1

def main():

   input_data()
   scan()
   solve()
   print(countB, volume)

if __name__ == "__main__":

   main()

</syntaxhighlight>