Cod sursa(job #407660)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 2 martie 2010 15:35:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<algorithm>
using namespace std;
#define DIM 100005

int sol,ind,a[DIM],b[DIM],t[DIM],n;
int poz;
char buff[DIM];

void pars (int &nr)
{
	nr=0;
	while(buff[poz]<'0' || '9'<buff[poz])
		if(++poz==DIM)
		{
			fread(buff,1,DIM,stdin);
			poz=0;
		}
	while('0'<=buff[poz] && buff[poz]<='9')
	{
		nr=nr*10+buff[poz]-'0';
		if(++poz==DIM)
		{
			fread(buff,1,DIM,stdin);
			poz=0;
		}
	}
}

void read ()
{
	int i;
	pars (n);
	for(i=1;i<=n;++i)
		pars (a[i]);
}

void show (int x)
{
	if(t[x])
		show (t[x]);
	printf("%d ",a[x]);
}

void solve ()
{
	int i,j;
	for(i=1;i<=n;++i)
	{
		for(j=1;j<i;++j)
			if(b[i]<b[j] && a[j]<a[i])
			{
				b[i]=b[j];
				t[i]=j;
			}
		++b[i];
		if(sol<b[i])
		{
			sol=b[i];
			ind=i;
		}
	}
	printf("%d\n",sol);
	show (ind);
}

int main ()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	read ();
	solve ();
	return 0;
}