Cod sursa(job #486607)

Utilizator ChallengeMurtaza Alexandru Challenge Data 22 septembrie 2010 10:22:18
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char InFile[]="subsir2.in";
const char OutFile[]="subsir2.out";
const int MaxN=5010;

ifstream fin(InFile);
ofstream fout(OutFile);

int v[MaxN],best[MaxN],p[MaxN],n,sol,soli,vmin;
vector<int> ind;
vector<int> ind1,ind2;

int main()
{
	v[0]=-1000010;
	best[0]=0;
	p[0]=0;
	fin>>n;
	for(register int i=1;i<=n;++i)
	{
		fin>>v[i];
		vmin=-1000010;
		for(register int j=0;j<i;++j)
		{
			if(v[j]<v[i])
			{
				if(best[i]<best[j])
				{
					best[i]=best[j];
					p[i]=j;
					vmin=v[j];
				}
				else if(best[i]==best[j] && vmin>v[j])
				{
					vmin=v[j];
					p[i]=j;
				}
			}
		}
		++best[i];
	}
	fin.close();
	
	sol=0;
	for(register int i=0;i<=n;++i)
	{
		if(best[i]>sol)
		{
			sol=best[i];
			soli=i;
		}
		else if(best[i]==sol)
		{
			bool better=true;
			int t1=soli,t2=i;
			while(t1 && t2)
			{
				ind1.push_back(t1);
				ind2.push_back(t2);
				t1=p[t1];
				t2=p[t2];
			}
			for(register int j=(int)ind1.size()-1;j>=0;--j)
			{
				if(v[ind1[j]]<v[ind1[j]])
				{
					break;
				}
				else if(v[ind1[j]]>v[ind1[j]])
				{
					better=false;
					break;
				}
			}
			if(better)
			{
				soli=i;
			}
			ind1.clear();
			ind2.clear();
		}
	}
	
	while(soli)
	{
		ind.push_back(soli);
		soli=p[soli];
	}
	
	sort(ind.begin(),ind.end());
	
	fout<<sol<<"\n";
	for(register int i=0;i<(int)ind.size();++i)
	{
		fout<<ind[i]<<" ";
	}
	fout.close();
	return 0;
}