Cod sursa(job #2063138)

Utilizator aditzu7Adrian Capraru aditzu7 Data 11 noiembrie 2017 09:44:58
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>

using namespace std;
int sol,mmax,nr[5001],ii,lmax,j, n,mx,i,a[10001],l[10001];
ifstream f("subsir2.in");
ofstream g("subsir2.out");
struct ob{
int val,ind;
}v[5001];
int main()
{f>>n;
   for(i=1;i<=n;i++){f>>a[i];v[i].val=10000001;}
l[n]=1;v[1].val=a[n];v[1].ind=n;
for(i=n-1;i>=1;i--){
    mx=0;
    for(j=i+1;j<=n;j++){
    if(a[j]>=a[i]&&l[j]>mx)mx=l[j];

    }
    l[i]=mx+1;
     if(v[l[i]].val>a[i]) v[l[i]].val=a[i],v[l[i]].ind=i;
    if(l[i]>lmax)lmax=l[i],ii=i;

}
g<<lmax<<'\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;*/
        for(i=lmax;i>=1;i--) g<<v[i].ind<<" ";
    return 0;
}