Cod sursa(job #1363225)

Utilizator RusuRadurusu radu RusuRadu Data 26 februarie 2015 20:04:16
Problema Hashuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<iostream>
using namespace std;
//ifstream cin("cuburi3.in");
//ofstream cout("cuburi3.out");
int main()
{
	int aux1,aux2,n,p=1;
	long c[10005],a[10005],lung[10005],urm[10005],b[10005],v[10005],lmax=0;
	int i,j,indice;
	cin>>n;
	for(i=1;i<=n;++i){
		cin>>a[i]>>b[i];c[i]=a[i];}
	
	for(i=1;i<=n;++i)	{	for(j=i+1;j<=n;++j)		if( b[i] < b[j]  )
				{
				aux1=b[i];   aux2=a[i]; 
				b[i]=b[j];	 a[i]=a[j];
				b[j]=aux1;	 a[j]=aux2;}}cout<<endl;
//for(i=1;i<=n;++i)
//cout<<a[i]<<" "<<b[i]<<endl;cout<<endl;

	for(i=n; i>=1; i--){
        lung[i]=1;
        for (j=n; j>i; j--)
        	
		if (a[i]>=a[j] && b[i]>b[j]) 
		if (lung[i]<lung[j]+1){
            	lung[i]=lung[j]+1;
            	urm[i]=j;
            if (lung[i]>lmax) {
				lmax=lung[i];
				indice=i;}
        }
    }
    int k=0;
    cout<<lmax<<" ";
	while(indice!=0){
		//cout<<a[indice]<<" ";
		k=k+a[indice];
		for(i=1;i<=n;++i)
			if( a[indice]==c[i])
			{ 
		v[p]=i;
		p++;
		c[i]=0;}
		
		indice=urm[indice];
	}
	
	cout<<k<<"\n";
	for(i=1;i<p;++i) cout<<v[i]<<"\n";
	
	return 0;
	
}