Cod sursa(job #2026585)

Utilizator Garen456Paun Tudor Garen456 Data 24 septembrie 2017 18:15:23
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>

using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,a[5005],q[5005],miz,mic,b[5005],cat;
bool capat[5005],c[5005][5005];
int main()
{   int i,j,mini,ok,ma;
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
    mini=1; q[1]=1; capat[1]=1;
    for(i=2;i<=n;++i)
    { ok=0; ma=0; capat[i]=1; q[i]=1;
        for(j=i-1;j>=1;--j)
        if(ok==1 && capat[j])
             {if(a[j]>ma &&  a[j]<=a[i])
             { capat[j]=0;
                if(q[j]+1<q[i])
             {  q[i]=q[j]+1;
               ma=a[j];
               c[i][j]=1;   // fout<<i<<"si"<<j<<";; ";
               capat[j]=0;
             }
             }
             }

       else   if(ok==0)
               if(a[j]<=a[i])
               { ok=1; ma=a[j];
                   capat[j]=0;
                   q[i]=q[j]+1; c[i][j]=1;
                 //  fout<<i<<"si"<<j<<"; ";
               }


       if(!ok)
            mini=i;
         //   fout<<"\n\n";


    }


 for(i=1;i<=n;++i)
        if(capat[i])
    if(miz==0)
           miz=q[i];
        else if(q[i]<miz)
            miz=q[i];
    fout<<miz<<"\n";
 for(i=1;i<=n;++i)
      if(capat[i] && q[i]==miz)
          if(mic==0)
            mic=i;
          else if(a[mic]>a[i])
            mic=i;
   b[miz]=mic; int minz;
   j=miz-1;
   while(j)
   {  minz=0;
       for(i=b[j+1]-1;i>=1;--i)
         if(!capat[i] && q[b[j+1]]-1==q[i] && a[b[j+1]]>a[i])
            if(c[b[j+1]][i])
          if(minz==0) minz=i;
         else if(a[minz]>a[i])
            minz=i;
         b[j]=minz;
      --j;
   }
   for(i=1;i<=miz;++i)
    fout<<b[i]<<" ";
    return 0;
}