# PBinfo #1070 – Deal – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
// 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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1070)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1070/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1070/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)