Cod sursa(job #415962)

Utilizator indestructiblecont de teste indestructible Data 12 martie 2010 00:03:47
Problema Subsir 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define N 5005
#define NR 1000005
int n,v[N],a[N],t[N],min,rez,poz_f;
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	int i,j,max,poz,poz2,poz2_f;
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	for (i=n; i>=1; i--)
	{
		max=N;
		poz=0;
		poz2=0;
		poz2_f=0;
		min=NR;
		for (j=i+1; j<=n; j++)
			if (v[j]>=v[i])
			{
				if (a[j]==max)
					if (v[j]<v[poz])
					{
						poz=j;
						t[i]=j;
					}
				if (a[j]<max)
				{
					max=a[j];
					a[i]=max+1;
					t[i]=j;
					poz=j;
				}
				if (v[j]<min)
				{
					min=v[j];
					poz2=j;
				}
				if (poz2<=poz)
					poz2_f=poz2;
			}
		if (max==N)
			a[i]=1;
		else
		{
			if (poz2_f!=poz)
			{
				a[i]=a[poz2_f]+1;
				t[i]=poz2_f;
			}
		}
		if (a[i]>rez)
		{
			rez=a[i];
			poz_f=i;
		}
	}
	printf("%d\n",rez);
	while (poz_f)
	{
		printf("%d ",poz_f);
		poz_f=t[poz_f];
	}
	return 0;
}