1070 - Deal

Vasilică are la grădiniţă N turnuri cu înălţimile h1, h2, …, hN. Când aşază în linie nişte turnuri, cel puţin două, astfel încât înălţimile lor să fie în ordine crescătoare, Vasilică spune că a construit un deal. Înălţimea dealului este egală cu înălţimea celui mai înalt turn folosit. Iată, de exemplu, că aşezând în ordine turnurile cu înălţimile 2 4 4 7 9 a format un deal cu înălţimea 9.

Vasilică şi-ar dori să aşeze în linie cele N turnuri, formând o succesiune de dealuri astfel încât suma înălţimilor dealurilor formate să fie maximă.

Cerinţă

Scrieţi un program care, cunoscând înălţimile celor N turnuri, va determina suma înălţimilor dealurilor ce se pot forma aşezând în linie cele N turnuri, maximă posibil.

Date de intrare

Fișierul de intrare deal.in conține pe prima linie numărul natural N. Pe cea de a doua linie se află N numere naturale separate prin spaţii, reprezentând înălţimile celor N turnuri.

Date de ieșire

Fișierul de ieșire deal.out va conține o singură linie pe care va fi scris un număr natural reprezentând cerinţa problemei.

Restricții și precizări

• 2 ≤ N ≤ 100 000
• 1 ≤ Înălţimile turnurilor ≤ 100 000
• Dacă după aranjarea turnurilor hi ≤ hi+1 atunci turnurile i şi i+1 fac parte din acelaşi deal.

Exemplu:

deal.in

7
10 2 2 2 7 5 2

deal.out

22

Explicație

O soluţie posibilă cu suma înălţimilor 22 ar fi: 2 10 2 5 2 2 7

S-au format trei dealuri: 2 10 (cu înălţimea 10) şi 2 5 (cu înălţimea 5) şi 2 2 7 cu înălțimea 7.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import numpy as np

nmax = 100001

def main():

   with open("deal.intxt", 'r') as f, open("deal.outtxt", 'w') as g:
       n = int(f.readline())
       w = np.zeros(nmax)
       v = np.zeros(nmax)
       i = 1
       x = 0
       st = 0
       dr = 0
       pdp = 0
       s = 0

       for i in range(1, nmax):
           w[i] = 0
       
       for i in range(1, n+1):
           x = int(f.readline())
           w[x] += 1
       
       for i in range(1, n+1):
           v[i] = w[i]
       
       st = 1
       dr = nmax - 1
       
       while w[st] == 0:
           st += 1
       
       while w[dr] == 0:
           dr -= 1
       
       while st != dr:
           if w[st] == 0:
               st += 1
           else:
               if w[dr] == 0:
                   dr -= 1
               else:
                   s += dr
                   w[st] -= 1
                   w[dr] -= 1
       
       pdp = (n - w[dr]) // 2 + 1 - (v[dr] - w[dr])
       
       if w[dr] // 2 <= pdp:
           s += dr * (w[dr] // 2)
       else:
           s += dr * pdp
       
       g.write(str(s))

</syntaxhighlight>