Raul: Pagină nouă: Vasilică are la grădiniţă `N` turnuri cu înălţimile `h₁`, `h₂`, …, `h_N`. 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...

2024-02-15T10:26:21Z

Pagină nouă: Vasilică are la grădiniţă <code>N</code> turnuri cu înălţimile <code>h1</code>, <code>h2</code>, …, <code>hN</code>. 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...

New page

Vasilică are la grădiniţă <code>N</code> turnuri cu înălţimile <code>h1</code>, <code>h2</code>, …, <code>hN</code>. 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 <code>2 4 4 7 9</code> a format un deal cu înălţimea <code>9</code>.

Vasilică şi-ar dori să aşeze în linie cele <code>N</code> 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 <code>N</code> turnuri, va determina suma înălţimilor dealurilor ce se pot forma aşezând în linie cele <code>N</code> turnuri, maximă posibil.

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

= Date de ieșire =
Fișierul de ieșire <code>deal.out</code> 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 =

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

= Exemplu: =
<code>deal.in</code>
7
10 2 2 2 7 5 2
<code>deal.out</code>
22

= Explicație =
O soluţie posibilă cu suma înălţimilor <code>22</code> ar fi: <code>2 10 2 5 2 2 7</code>

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

== Î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>

1070 - Deal - Revision history