Cod sursa(job #1046236)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 2 decembrie 2013 19:42:09
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <iostream>

using namespace std;
#define maxn 101

int v[maxn], best[maxn], last[maxn], sol[maxn], vcb[maxn];

int main () {

    FILE *f, *g;
    f = fopen( "scmax.in", "r" );
    g = fopen( "scmax.out", "w" );

    int n, elmax = 0, poz, psol, pvcb = 0;

    fscanf( f, "%d", &n );

    for( int i = 0 ; i < n ; ++i )
        fscanf( f, "%d", &v[i] );

    vcb[0] = 0;
    pvcb = 1;

    for( int i = 1 ; i < n ; ++i ) {

        int index = pvcb;
        while( pvcb >0 && v[vcb[pvcb]] >= v[i] )
            --pvcb;
        ++pvcb;

        best[i] = pvcb;
        vcb[pvcb] = i;
        if( pvcb > 0 )
            last[i] = vcb[pvcb - 1];
        else
            last[i] = i;
        if( best[i] > elmax )
            elmax = best[i], poz = i;
        pvcb = max( pvcb, index);
    }

    for( int i = 0 ; i < pvcb ; ++i )
        cout<<vcb[i]<<" ";

    psol = 0;
    int k = best[poz];

    while( k ) {
        sol[psol] = v[poz];
        psol++;
        --k;
        poz = last[poz];
    }

    fprintf( g, "%d\n", elmax );

    for( int i = psol - 1 ; i >= 0 ; --i )
        fprintf( g, "%d ", sol[i] );

    fclose( f );
    fclose( g );

    return 0;

}