Cod sursa(job #1042880)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 27 noiembrie 2013 19:25:31
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>

using namespace std;
FILE *f=fopen("subsir2.in","r");
FILE *g=fopen("subsir2.out","w");

int best[5004],v[5004],i,j,n,min1,mn,ok,ll,t[5004],r,o,mm;

void solve (int a)
{
fprintf(g,"%d ",a);
if (a!=t[a])solve(t[a]);
}

int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d",&v[i]);
best[n]=1;
t[n]=n;
for(i=n-1;i>=1;i--)
{
ok=0; min1=1000005;
mn=1000005;
for(j=i+1;j<=n;j++)
if (v[j]>=v[i] && v[j]<mn)
{
 if (min1>=best[j]){min1=best[j];ll=j;}
mn=v[j];
ok=1;
}
if (ok==1){best[i]=min1+1;t[i]=ll;}
else {best[i]=1;t[i]=i;}
if (best[i]>r){r=best[i];o=i;mm=v[i];}
else if (best[i]==r && v[i]<mm){r=best[i];o=i;mm=v[i];}
}

fprintf(g,"%d\n",r);
solve(o);
fclose(g);
return 0;
}