Cod sursa(job #1951523)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 3 aprilie 2017 17:59:41
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#define inf 1000000000

long n,i,j,a[5005],l[5005],t[5005],min,max;
long mark[5005],p,lmin,valmin;

int main(){
    FILE *fin, *fout;
    fin = fopen("subsir2.in","r");
    fout = fopen("subsir2.out","w");

    fscanf(fin, "%ld",&n);
    for (i=1;i<=n;i++)
        fscanf(fin, "%ld",&a[i]);

    l[n]=1;
    t[n]=0;
    for (i=n-1;i;i--){
        min=inf;
        lmin=n+1;

        p=0;
        for (j=i+1;j<=n;j++)
            if (a[j]>=a[i]){
               if (a[j]<min){
                  min=a[j];
                  if (l[j]<lmin){lmin=l[j];valmin=a[j];p=j;}
                  else if (l[j]==lmin)
                          if (a[j]<valmin){valmin=a[j];p=j;}
               }
               mark[j]=1;
            }
        if (p){
          l[i]=lmin+1;t[i]=p;
        }
        else {t[i]=0;l[i]=1;}
    }
    min=n+1;
    for (i=1;i<=n;i++)
        if (!mark[i]){
           if (l[i]<min){min=l[i];p=i;}
           else if (l[i]==min&&a[i]<a[p])p=i;
        }
    fprintf(fout, "%ld\n",min);

    while (p){
          fprintf(fout, "%ld ",p);
          p=t[p];
    }

    fprintf(fout, "\n");
  fclose (fin);
  fclose (fout);
return 0;
}