Cod sursa(job #458380)

Utilizator aladinaladin aladinn aladin Data 24 mai 2010 19:32:26
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#define N 1000003
int n,i,v[5004],x[5004],l[5004],j,sol,min=N;

int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i) scanf ("%d",&v[i]);
	min=-N;
	for (i=n;i>0;--i)
		if (v[i]>min)
			x[i]=1,min=v[i];
	sol=-1;	
	min=N;
	for (i=1;i<=n;++i)
		if (v[i]<min)
			l[i]=-1,min=v[i];
	for (i=n-1;i>0;--i)	
		
	{
		int max=N,ord=0;
		if (x[i]==0)
		{
			
		min=N;
		
		for (j=i+1;j<=n;++j)
		{
			if ((min>v[j]) && (v[j]>v[i]) && (x[j]<=max))
			{
				if (x[j]<max)
					max=x[j],ord=j; else
						ord=j;
			}
			
				
			if ((v[j]<min) && (v[j]>=v[i])) min=v[j];
			if (min<=v[i]) break;
		}
		x[i]=max+1;
		}
		if (l[i]==-1)
		{
			if (sol==-1)
				sol=i;
			
		 if (x[i]<x[sol]) sol=i; else
			if ((x[i]==x[sol]) && (v[i]<v[sol]))
				sol=i;
		}
		l[i]=ord;
	}
if ((sol==-1) || (x[sol]>x[n])) sol=n;	else
if ((x[sol]==x[n]) && (v[sol]>v[n])) sol=n;
printf("%d\n",x[sol]);
do
{
printf("%d ",sol);
sol=l[sol];
}
while (sol>0);
return 0;}