Cod sursa(job #2026572)

Utilizator Garen456Paun Tudor Garen456 Data 24 septembrie 2017 17:53:19
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 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];
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>=mini;--j)
        if(ok==1)
             {if(a[j]>ma &&  a[j]<a[i])
                if(q[j]+1<q[i])
             {  q[i]=q[j]+1;
               ma=a[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;
               }


       if(!ok)
            mini=i;


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