Cod sursa(job #2063320)

Utilizator aditzu7Adrian Capraru aditzu7 Data 11 noiembrie 2017 10:46:54
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;
int mmin,use[5002],sol,mmax=0,nr[5002],ii,lmax,j, n,mx,i,a[10001],l[10001];
ifstream f("subsir2.in");
ofstream g("subsir2.out");

int main()
{f>>n;a[n+1]=-1000001;
   for(i=1;i<=n;i++) f>>a[i];

for(i=n;i>=1;i--){
    mmin=1000001;
    for(j=i+1;j<=n;j++)
    if(a[j]>=a[i]&&a[j]<mmin){
mmin=min(mmin,a[j]);
l[i]=min(l[i],l[j]+1);
if(!l[i]) l[i]=l[j]+1;
    }
   if(l[i]==0) l[i]=1;
}
mmin=1000001;
mmax=1000001;
for(i=1;i<=n;i++)
{if(a[i]<mmin) mmin=a[i],mmax=min(mmax,l[i]);

}

g<<mmax<<'\n';
i=ii;
/*

for(i=n;i>=1;i--){
      if(l[i]==1)  {nr[i]=1;continue;}
    for(j=i+1;j<=n;j++){
    if(l[j]+1==l[i]&&a[j]>a[i]) {nr[i]+=nr[j];}
nr[i]=nr[i]%9901;
    }
}
for(i=1;i<=n;i++)mmax=max(mmax,l[i]);
    for(i=1;i<=n;i++)
        if(l[i]==mmax)sol=(sol+nr[i])%9901;
        g<<sol;*/
ii=0;int aa=-1000001;
    int k=mmax;
    while(k){mmax=mmin=1000001;

       for(j=ii+1;j<=n;j++)
        if(l[j]==k&&aa<=a[j]&&mmin>a[j]) mmin=a[j],ii=j;


       else if(a[j]>=aa&&a[j]<mmin) mmin=a[j];
       g<<ii<<" ";
//use[ii]=1;
k--;
       aa=a[ii];
    }

    return 0;
}