Cod sursa(job #369439)

Utilizator aghamatMorariu Razvan aghamat Data 28 noiembrie 2009 13:33:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>

#define DIM 100000

int v[DIM], l[DIM], n, i, k, max, t, pozitie;
char buff[DIM];

inline void cit (int &nr)
{
    for (nr=0; buff[pozitie]<'0' || buff[pozitie]>'9'; )
        if (++pozitie==DIM)
        {
            fread (buff,1,DIM,stdin);
            pozitie=0;
        }
    for ( ; '0'<=buff[pozitie] && buff[pozitie]<='9'; )
    {
        nr=nr*10+buff[pozitie]-'0';
        if (++pozitie==DIM)
        {
            fread (buff,1,DIM,stdin);
            pozitie=0;
        }
     }
}

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	cit(n);
	for (i=1;i<=n;++i)
		cit(v[i]);
    l[n]=1;
    for (k=n-1;k>=1;--k)
        {
            max=0;
            for (i=k+1;i<=n;++i)
                if (v[i]>v[k] && l[i]>max)
                    max=l[i];
            l[k]=max+1;
            }
    max=l[1];
    t=1;
    for (k=1;k<=n;++k)
        if (l[k]>max)
            {
                max=l[k];
                t=k;
                }
    printf("%ld\n",max);
    printf("%ld ",v[t]);
    for (i=t+1;i<=n;++i)
        if (v[i]>v[t] && l[i]==max-1)
            {
            printf("%ld ",v[i]);    
            --max;    
                }
    return 0;
    }