Cod sursa(job #588164)
Utilizator | Enal Gemaledin Blaugranas | Data | 7 mai 2011 09:52:15 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include<fstream.h>
#define N 100001
long a[N],b[N],p[N],i,j,k,c,m=0,n,u,v;
int main()
{ifstream f("scmax.in");
ofstream g("scmax.out");
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
a[0]=b[0]=0;
for(i=1;i<=n;i++)
{if(a[b[m]]<a[i])
p[i]=b[m],b[++m]=i;
for(j=0,k=m;j<k;)
{c=(j+k)/2;
if(a[b[c]]<a[i])
j=c+1;
else
k=c;}
if(a[i]<a[b[j]])
{if(j>0)
p[i]=b[j-1];
b[j]=i;}}
for(u=m,v=b[m];u--;v=p[v])
b[u]=v;
g<<m<<"\n";
for(i=0;i<m;i++)
g<<a[b[i]]<<" ";
f.close();
g.close();
return 0;}