Cod sursa(job #574807)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 7 aprilie 2011 16:03:21
Problema Subsir 2 Scor 19
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
// infoarena: problema/subsir2 //
#include <fstream>
#include <iostream>
using namespace std;

ifstream in("subsir2.in");
ofstream out("subsir2.out");

const int MAXN = 5010;

int l[MAXN],r[MAXN],x[MAXN],i,j,n,m,mi,mr,k,v,prev;

int main()
{
	in>>n;
	for(i=1; i<=n; i++)
		in>>x[i], r[i] = l[i] = 1;
		
	l[1] = 1;
	for(i=2; i<=n; i++)
		for(j=1; j<i; j++)
			if(x[j] <= x[i] && (l[i] == 0 || l[i]<l[j]+1))
				l[i] = l[j]+1;
	r[n] = 1;
	for(i=n-1; i>=1; i--)
		for(j=i+1; j<=n; j++)
			if(x[i] <= x[j] && (r[i] == 0 || r[i]<r[j]+1))
				r[i] = r[j] + 1;
				
	
	/*for(i=1; i<=n; i++)
		out<<l[i]<<' ';
	out<<'\n';
	for(i=1; i<=n; i++)
		out<<r[i]<<' ';
	out<<"\n\n\n";*/
				
				
	for(i=1; i<=n; i++)
		if(!m || m>l[i]+r[i]-1)
			m = l[i] + r[i] -1, mi=i;
	out<<m<<'\n';
	
	prev = -1<<29;
	mi = 1;
	for(i=1; i<=m; i++)
	{
		cerr<<i<<": ";
		mr = 0;
		for(j=mi; j<=n; j++)
			if(l[j]+r[j]-1 == m && prev <= x[j] && l[j] == i && (x[mr] > x[j] || !mr))
				mr=j, cerr<<j<<' ';
		out<<mr<<' ';
		cerr<<'\n';
		prev = x[mr];
		mi = mr+1;
	}
	
	return 0;
}