Mai intai trebuie sa te autentifici.

Cod sursa(job #635492)

Utilizator comananamariaComan Ana-Maria comananamaria Data 19 noiembrie 2011 12:13:40
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>

using namespace std;

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

int n,v[5001],l[5001],sol[5001],vi[5001];

int main(){
	in>>n;
	for(int i=1;i<=n;i++)
		in>>v[i];
	l[n]=1;
	for(int i=n-1;i>=1;i--){
		int max=0;
		for(int j=i+1;j<=n;j++)
			if(v[i]<v[j])
				if(max<l[j])
					max=l[j];
		l[i]=max+1;
	}
	int lmax=l[1],pmax=1,ult=v[1];
	for(int i=2;i<=n;i++)
		if(lmax<l[i]){
			lmax=l[i];
			pmax=i;
			ult=v[i];
		}
		else
			if(lmax==l[i] && ult>=v[i]){
				pmax=i;
				ult=v[i];
			}
	out<<lmax<<endl;
	sol[1]=v[pmax];
	vi[1]=pmax;
	int max=lmax;
	lmax--;
	int k=1;
	for(int j=pmax+1;lmax>0;j++){
		for(int i=j;i<=n;i++)
			if(lmax==l[i] && v[i]>ult){
				k++;
				sol[k]=v[i];
				vi[k]=i;
				ult=v[i];
			}
			else
				if(lmax==l[i] && v[i]<sol[k] && v[i]>sol[k-1]){
					sol[k]=v[i];
					vi[k]=i;
				}
		lmax--;
		ult=sol[k];
	}
	for(int i=1;i<=max;i++)
		out<<vi[i]<<" ";
	return 0;
}