Cod sursa(job #361453)

Utilizator mgntMarius B mgnt Data 5 noiembrie 2009 10:12:31
Problema Subsir 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;

int const maxn = 5000;
int const maxv =   1000 * 1000;
int const minv = - 1000 * 1000;

typedef int A1 [1+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; ++ n; A[0]=minv-1;
  for ( i=1; n>i; ++i ) { is >> A[i]; }
  
  for ( i=n-1; 0<=i; --i ) {
    
    l=1+maxn;a=A[i]; b= 1+maxv; y=-1;
    
    for ( k=1+i; n>k; ++k )
      if ( a<=A[k] && b>A[k] ) {
        b=A[k];
        if (l>L[k]) {
          l=L[k]; y=k;
        }
      }

    if ( 1+maxn != l ) 
       { L[i]=1+l; }
    else
       { L[i]=1; }

    I[i]=y;
  }

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

  return 0;
}