Mai intai trebuie sa te autentifici.

Cod sursa(job #203746)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 19 august 2008 11:45:53
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#define min(x,y) x<y ? x:y

#define IN  "subsir2.in"
#define OUT "subsir2.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<13

int N;
short int A[N_MAX],T[N_MAX];
int V[N_MAX];

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d\n", &N);
	FOR(i,1,N) scanf("%d", &V[i]);
}

void solve()
{
	int best(0),minim(1<<21);
	A[0] = 1<<13;
	V[0] = 1<<21;
	for(int i=N;i>=1;--i)
	{
		FOR(j,i+1,N)
			if(V[j] >= V[i])
			{
				if(V[j] < minim && (A[j] < A[best] || (A[j] == A[best] && V[j] < V[best])) )
					best = j;
				minim = min(minim,V[j]);
			}	
		if(best)
			A[i] = A[best] + 1,
			T[i] = best;
		else
			A[i] = 1;
		best = 0;
		minim = 1<<21;	
	}	
	
	FOR(i,1,N)
	{
		if(V[i] < minim && (A[i] < A[best] ||  (A[i] == A[best] && V[i] < V[best])))
			best = i;
		minim = min(minim,V[i]);
	}	
	
	printf("%d\n", A[best]);
	int rez = best;
	FOR(i,1,A[rez])
	{
		printf("%d ",best);
		best = T[best];
	}
}

int main()
{
	scan();
	solve();
	return 0;
}