Cod sursa(job #2167906)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 14 martie 2018 01:28:00
Problema Subsir crescator maximal Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

#define NMAX 100003
long long N, K, Lmax, a[NMAX], st[NMAX], l[NMAX];

int Binary_search(int val)
{
    int l, r, m; /// left, right, mij
    l = 1, r = K;

    if( val < st[1] )
        return 0;

    while( l <= r )
    {
        m = l + (r-l)/2;
        if( st[m] < val && val <= st[m+1] ) return m;
        else if( st[m] < val ) l = m+1;
             else r = m-1;
    }

    st[++K] = val;
    return K-1;
}

void LIS()
{
    int pos;
    K = 0;
    for(int i = 1 ; i <= N ; ++i)
    {
        pos = Binary_search(a[i]);
        l[i] = pos+1;
        st[pos+1] = ( a[i] < st[pos+1] )? a[i]: st[pos+1] ;
    }
    Lmax = K;

    for(int i = N ; i >= 1 && K != 0 ; --i)
        if( l[i] == K ) st[K--] = a[i];
}

int main()
{
    f >> N;
    for(int i = 1 ; i <= N ; ++i)
        f >> a[i];
    LIS();

    g << Lmax << '\n';
    for(int i = 1 ; i <= Lmax ; ++i)
        g << st[i] << ' ';

    if( Lmax <= 0 )
        for(int i = 1 ; i >= N ; ++i)
    return 0;
}