Cod sursa(job #252930)

Utilizator MciprianMMarginean Ninu Ciprian MciprianM Data 5 februarie 2009 09:01:13
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<fstream>
using namespace std;
int a[100000];
int b[100000],l;
int main(){
  int i, n, pas, j;
  ifstream f("scmax.in");
  ofstream g("scmax.out");
  f>>n;
  for(i=0;i<n;i++)
    f>>a[i];
  f.close();
  b[l++]=a[0];
  for(i=1;i<n;i++)
  {
    for(pas=1;pas<=l;pas<<=1);
    for(j=l-1;pas;pas>>=1)
      if(j-pas>=0&&b[j-pas]>=a[i])
        j-=pas;
    if(j==l-1&&b[j]<a[i])  b[l++]=a[i];
    else b[j]=a[i];
  }
  g<<l<<'\n';
  for(i=0;i<l;i++)
    g<<b[i]<<' ';
  g<<'\n';
  g.close();
  return 0;
}