Cod sursa(job #1199588)

Utilizator azkabancont-vechi azkaban Data 19 iunie 2014 18:29:19
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");

typedef struct celula {
                       long info; 
                       celula* next;
                       } *lista;
                       
void add(long val, lista &p)
{
  lista r=new celula;
  r->info=val;
  r->next=p;
  p=r;
} 
     
long n,i,j,A[100013],D[100013],Ssol[100013],sol(0),maxim(-99999),aux,ok(0);
lista lda[100000];
int main()
{
    memset(D,0,sizeof(D));
    cin>>n;
    for (i=1;i<=n;++i) cin>>A[i];
    D[1]=1;
    add(A[1],lda[1]);
    for (i=2;i<=n;++i){
                       maxim=0;
                       for (j=1; j<=i-1;++j) if (A[j]<A[i] && maxim<D[j]) maxim=D[j];                 
                       D[i]=maxim+1;
                       add(A[i],lda[D[i]]);
                      }
    for (i=1;i<=n;++i) maxim=max(maxim,D[i]);
    cout<<maxim<<"\n";
    long valoare(99999999);
    while (maxim>0) {
                     aux=-99999999;
                     for(lista r=lda[maxim];r;r=r->next) 
                             if (r->info<valoare) 
                                        aux=max(r->info,aux);
                     Ssol[++sol]=aux;
                     valoare=aux;
                     --maxim;
                     }
   for (i=sol;i>=1;--i) cout<<Ssol[i]<<" ";
return 0;
}