Cod sursa(job #1115943)

Utilizator robertstrecheStreche Robert robertstreche Data 22 februarie 2014 11:03:55
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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];

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;
     }
      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';

     pozprec=poz-1;

     for (i=ma;i>=1;i--)
      {
          nr=inf;

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

           g<<poz<<" ";
           pozprec=poz;
        }

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