Cod sursa(job #291657)
Utilizator | Dumitrescu Victor victor_bla_bla | Data | 30 martie 2009 09:50:24 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include<fstream.h>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long v[100005],p[100005],q[100005],n,l,i;
const long s=2000000001;
long cautare(long k,long x, long y)
{long m=x+(y-x)/2;
if (x==y)
{if (y>l) q[++l+1]=s;
q[x]=k;
return x;}
else if (k<=q[m])
return cautare(k,x,m);
else return cautare(k,m+1,y);}
int main()
{fin>>n;
for (i=1;i<=n;i++)
fin>>v[i];
q[1]=s;l=0;
for (i=1;i<=n;i++)
p[i]=cautare(v[i],1,l+1);
fout<<l;
fout.close();
return 0;}