Cod sursa(job #1097781)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 3 februarie 2014 22:18:09
Problema Subsir crescator maximal Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
using namespace std;
int i,n,best[100005],aux[100005],a[100005],sol,posst,laux;

int cauta(int x) {
    int l=0,r=laux;
    while (l<=r) {
          int mid=(l+r)/2;
          if (aux[mid]>x) l=mid+1;
           else r=mid-1;
           }
    return(r);
}

int main(void) {
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    aux[0]=2000000001;
    fin>>n;
    for (i=1; i<=n; ++i) fin>>a[i];
    
    best[n]=1; aux[1]=a[n];
    for (i=n-1; i>=1; --i) {
           int lung=cauta(a[i]);
           best[i]=lung+1;
           aux[lung+1]=max(aux[lung+1],a[i]);
           if (best[i]>sol) { sol=best[i]; posst=i; ++laux; }
           }
    
   fout<<sol<<"\n";
   int v=a[posst]-1;
   for (i=posst-1; i<=n; ++i)
    if (a[i]>v&&best[i]==sol){ fout<<a[i]<<" "; v=a[i]; --sol; }
 return(0);
}