Cod sursa(job #744740)

Utilizator andrey13Letcanu Andrei andrey13 Data 9 mai 2012 16:15:27
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<cstdio>

using namespace std;

int L,a[100000],q[100000],p[100000],i,n,max,k;
int bin(int x,int st,int dr){
    int m,poz;
     poz=0;
  while (st<=dr && poz==0){
    m=(st+dr)/2;
    if (q[m]==x) poz=m;
    else if (q[m]>x) dr = m-1;
         else st = m+1;
  }
    if (poz==0) poz=st;
    if  (st>L) L++;
    q[poz]=x;
    return poz;
}

void scrie ( int i, int x, int max){

  if(i>0){
    if (a[i]<x && p[i]==max) {
       scrie (i-1, a[i], max-1);
       printf("%d ", a[i]);
    }
    else scrie (i-1, x, max);
    }
}


int main(){
   freopen("scmax.in","r",stdin);
   freopen("scmax.out","w",stdout);
   scanf("%d",&n);
   for(i=1;i<=n;i++)scanf("%d",&a[i]);
   for(i=1;i<=n;i++){
      p[i]=bin(a[i],1,L);
      if(p[i]>max){
        max=p[i];
        k=i;}}
    printf("%d\n",L);
scrie(k,2000000001,max);
return 0;
   }