Cod sursa(job #1115960)

Utilizator robertstrecheStreche Robert robertstreche Data 22 februarie 2014 11:21:44
Problema Subsir 2 Scor 42
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#define lmax 5001
#define inf 10000000

using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

long long i,j,n,mi,ma,maa=inf,poz,pozprec,nr;
long long a[lmax],b[lmax],urm[lmax];

int main()
{
    f>>n;

    for (i=1;i<=n;i++)
         f>>a[i];

     b[n]=1;

     for (i=n-1;i>=1;i--)
     {
         mi=inf;
         poz=0;

        for (j=1+i;j<=n;j++)
          if (a[i]<a[j] && a[j]<mi)
           {
              poz=j;
              mi=j;
           }

         b[i]=b[poz]+1;
         urm[i]=poz;
     }
      mi=inf;

     for (i=1;i<=n;i++)
       if (a[i]<mi)
        {
            mi=a[i];
            ma=b[i];
            poz=i;
        }

      //for (i=1;i<=n;i++)
      //g<<b[i]<<" ";

      g<<ma<<'\n';

     for (i=ma;i>=1;i--)
      {
           g<<poz<<" ";
           poz=urm[poz];
      }

    f.close();
    g.close();
}