Cod sursa(job #1218733)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 12 august 2014 13:55:55
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define Nmax 100005
#define INF 0x3f3f3f3f

using namespace std;
int N,v[Nmax],best[Nmax],vf,daddy[Nmax],poz[Nmax];
vector<int> sol;

void read( void )
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        scanf("%d",&v[i]);
}

void solve( void )
{
    int pz;
    for(int i = 1; i <= 100004; ++i)
        best[i] = 2 * INF;
    best[0] = 0;
    for(int i = 1; i <= N; ++i)
    {
        pz = lower_bound(best+1,best+vf+1,v[i]) - best;
        if(v[i] < best[pz])
        {
            best[pz] = v[i];
            poz[pz] = i;
        }
        daddy[i] = poz[pz - 1];
        if(pz > vf)
            ++vf;
    }
}

void print( void )
{
    printf("%d\n",vf);
    int crt = poz[vf];
    for(int i = 1; i <= vf; ++i)
    {
        sol.push_back(v[crt]);
        crt = daddy[crt];
    }
    for(vector<int>::reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it)
        printf("%d ", *it);
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);

    read();
    solve();
    print();

    return 0;
}