Cod sursa(job #361348)

Utilizator mgntMarius B mgnt Data 4 noiembrie 2009 19:05:02
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
using namespace std;

int const maxn = 5000;

typedef int A1 [maxn];
A1 A,L,I;

int
main ( ) {
  ifstream is ( "subsir2.in" );
  ofstream os ( "subsir2.out" );
  int n,i,k,l,a,b,y;
  is >> n;
  for ( i=0; n>i; ++i ) { is >> A[i]; }
  
  for ( i=n-1; 0<=i; --i ) {
    
    l=0;a=A[i]; b=0; y=-1;
    
    for ( k=n-1; k>i; --k )
      if ( a<=A[k] )
        if ( (l<L[k]) || ( (l==L[k]) && (A[k]<=b) ) ) {
          l=L[k]; b=A[k]; y=k;
        }
    
    L[i]=1+l; I[i]=y;
  }

  l=L[n-1]; y=i-1;
  for ( i=n-1; i>=0; --i )
    if ( l<=L[i] ) { l=L[i]; y=i; }

  os << l << endl; os << 1+y;
  for ( i=1; i<l; ++i ) {
    y=I[y]; os << ' ' << 1+y;
  }
  os << endl;

  return 0;
}