Cod sursa(job #1115904)

Utilizator robertstrecheStreche Robert robertstreche Data 22 februarie 2014 10:23:54
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#define lmax 5001
#define inf 100000000

using namespace std;

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

int i,j,n,ma,poz,pozprec,nr;
int 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--)
      for (j=1+i;j<=n;j++)
        if (a[i]<=a[j] && b[i]<b[j]+1)
         b[i]=b[j]+1;

     for (i=1;i<=n;i++)
       if (b[i]>ma)
        ma=b[i];



      g<<ma<<'\n';

     pozprec=0;

     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();
}