Cod sursa(job #1453732)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 24 iunie 2015 15:08:48
Problema Subsir 2 Scor 86
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
using namespace std;
int lmin[5001],v[5001],urm[5001],sol[5001];
int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int n,maxi,i,j,mini,poz;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        mini=10000;
        maxi=-2000000000;
        for(j=i-1;j>=0;j--)
            if(v[j]<=v[i])
                if(v[j]>maxi){
                    maxi=v[j];
                    if(lmin[j]<mini){
                        mini=lmin[j];
                        urm[i]=j;
                    }
                    else
                        if(lmin[j]==mini&&v[j]<v[urm[i]])
                            urm[i]=j;
                }
        lmin[i]=mini+1;
    }
    maxi=-2000000000;
    mini=100000;
    for(i=n;i>=1;i--)
        if(v[i]>maxi){
            maxi=v[i];
            if(lmin[i]<mini){
                mini=lmin[i];
                poz=i;
            }
        }
    printf("%d\n",mini);
    for(i=1;i<=mini;i++){
        sol[i]=poz;
        poz=urm[poz];
    }
    for(i=mini;i>=1;i--)
        printf("%d ",sol[i]);
    return 0;
}