# PBinfo #3521 – Up – Rezolvare C++

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

## Enunț

Mario a primit de ziua lui un nou joc video, “ Up “. În acest joc are n baloane numerotate de la 1 la n. Fiecare balon i ( 1 ≤ i ≤ n ) se află la o distanță di de sol. La începutul jocului Mario poate alege oricare dintre cele n baloane pe care să se poziționeze. Aflându-se la un moment dat pe un balon cu numărul de ordine l, băiatul poare sări pe oricare alt balon cu indicele t doar daca l < t și dl < dt. Jocul continuă până când nu mai există baloane care să respecte condiția dată. Numărul de baloane pe care jucatorul sare este egal cu scorul obținut.

Cerința
  Mario, curios din fire, vrea să afle care este scorul maxim pe care l-ar putea obține în joc.

Date de intrare
Fișierul de intrare up.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire up.out va conține un număr natural k care reprezintă scorul maxim obținut la joc.

Restricții și precizări

1 ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:
up.in

10
10 2 7 5 4 6 7 1 8 9
up.out

6
Explicație
O posibilitate de a obține scorul maxim este de a sări pe următoarele baloane: 2 4 6 7 9 10

## Cod sursă C++

```cpp
#include <fstream>
#define NM 100000
using namespace std;
ifstream f("up.in");
ofstream g("up.out");
int n,L,st,dr,i,mijl;
int x[NM],a[NM];
int main()
{
    f>>n;
    L=0;
    for(i=1; i<=n; i++)
    {
        f>>x[i];
        st=1;
        dr=L;
        while(st<=dr)
        {
            mijl=(st+dr)/2;
            if(x[a[mijl]]<x[i])
                st=mijl+1;
            else
                dr=mijl-1;
        }
        a[st]=i;
        L=max(L,st);
    }
    g<<L<<'\n';
    return 0;
}
```

## Resurse

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