Cod sursa(job #1369622)

Utilizator gedicaAlpaca Gedit gedica Data 3 martie 2015 10:13:00
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>

using namespace std;

const int NMAX= 5000, inf= 1000000;

ifstream in( "subsir2.in" );
ofstream out( "subsir2.out" );

int v[NMAX+1], l[NMAX+1], r[NMAX+1];

int main()
{
    int N;
    in >> N;

    for( int i= 1; i<=N; ++i )
    {
        in >> v[i];
    }

    ++N;
    v[0]= -inf;
    v[N]= inf;

    for( int i= 0; i<=N; ++i )
    {
        r[i]= -1;
    }

    for( int i= N-1; i>=0; --i )
    {
        int mini = inf+1;
        l[i]= NMAX+1;

        for( int j= i+1; j<=N; ++j )
        {
            if( ( v[j] >= v[i] ) && ( v[j] < mini ) )
            {

                if( l[i]-1 > l[j] )
                {
                    l[i]= l[j] + 1;
                    r[i]= j;
                }
                else if( l[i]==l[j]+1 && v[i] < v[ r[i] ] )
                {
                    r[i]= j;
                }

                mini= v[j];
            }
        }
    }
    out << l[0]-1 << '\n';

    int poz=0;
    while( r[poz]!=N )
    {
        out << r[poz] << ' ';
        poz= r[poz];
    }
    return 0;
}