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 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 h_i ≤ h_i+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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Deal:

// sursa de 100 puncte Ciprian Chesca


#include <fstream>
#define nmax 100001

using namespace std;


int main()
{
ifstream f("deal.in");
ofstream g("deal.out");


long n,w[nmax],v[nmax],i,x,st,dr,pdp;
long long s=0;


f>>n;
for(i=1;i<nmax;i++) 
    w[i]=0;
for(i=1;i<=n;i++)
    {f>>x;w[x]++;}
for(i=1;i<=n;i++)
    v[i]=w[i];  
    

st=1;dr=nmax-1;
while (w[st]==0) st++;
while (w[dr]==0) dr--;

while (st!=dr)
{
    if (w[st]==0) st++;
        else 
            if (w[dr]==0) dr--;
                else {s=s+dr;w[st]--;w[dr]--;}
}

pdp=(n-w[dr])/2+1-(v[dr]-w[dr]);

if (w[dr]/2<=pdp) s=s+dr*(w[dr]/2);
  else s=s+dr*pdp;

g<<s;

f.close();
g.close();

return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1070 Deal

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1070 Deal de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1070 Deal