Cod sursa(job #1996373)

Utilizator victoreVictor Popa victore Data 1 iulie 2017 12:26:04
Problema Subsir 2 Scor 69
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<cstdio>

using namespace std;

const int nmax=5005;

int v[nmax],d[nmax],t[nmax];
bool used[nmax];

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    d[n]=1;
    t[n]=n;
    int minim,maxim;
    d[n]=1;
    t[n]=n;
    v[0]=1000005;
    for(i=n-1;i;--i)
    {
        d[i]=1;
        t[i]=i;
        maxim=5005;
        minim=0;
        for(j=i+1;j<=n;++j)
            if(v[i]<=v[j])
            {
                used[j]=1;
                if(v[j]<v[minim]&&d[j]<=maxim)
                {
                    minim=j;
                    maxim=d[j];
                    t[i]=j;
                    used[j]=1;
                }
            }
        if(maxim!=5005)
            d[i]=maxim+1;
    }
    maxim=0;
    for(i=1;i<=n;++i)
        if(!used[i])
        {
            if(maxim==0||d[i]<d[maxim])
                maxim=i;
            else if(d[i]==d[maxim]&&v[i]<v[maxim]);
                maxim=i;
        }
    printf("%d\n",d[maxim]);
    while(t[maxim]!=maxim)
    {
        printf("%d ",maxim);
        maxim=t[maxim];
    }
    printf("%d",maxim);
}