Cod sursa(job #312367)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 5 mai 2009 20:32:54
Problema Subsir 2 Scor 22
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
# include <stdio.h>
int a[10000],b[10000],c[10000],d[10000],i,j,max,min,x,n,k,p,y,m;
int main ()
{
freopen ("subsir2.in","r",stdin);
freopen ("subsir2.out","w",stdout);
scanf ("%i",&n);
for (i=1;i<=n;i++)
scanf ("%i",&a[i]);
b[1]=1;
for (i=2;i<=n;i++)
{
max=-1001;
for(j=1;j<i;j++)
if (a[j]<=a[i] && max<b[j])
max=b[j];
if (max!=-1001)
b[i]=max+1;
else
b[i]=1;
}
d[n]=1;
for (i=n-1;i>=1;i--)
{
max=-1001;
for (j=i+1;j<=n;j++)
if (a[j]>=a[i] && d[j]>max)
max=d[j];
if (max!=-1001)
d[i]=max+1;
else
d[i]=1;
}



min=1001;
for (i=1;i<=n;i++)
if (b[i]+d[i]-1<min)
min=b[i]+d[i]-1;
printf ("%i\n",min);
max=-1001;
for (i=1;i<=n;i++)
if (b[i]>max)
max=b[i];
k=min;;
m=min;
x=1001;y=1001;
while (k)
{
min=1001;
for (i=1;i<=n;i++)
if (b[i]==k && a[i]<x && i<y && a[i]<min)
{
min=a[i];
p=i;
}

c[k]=p;
x=min;
y=p;

k--;
}
for (i=1;i<=m;i++)
printf ("%i ",c[i]);
return 0;
}