Cod sursa(job #1126627)

Utilizator UngureanuRobertUngureanu Robert Mihail UngureanuRobert Data 27 februarie 2014 08:23:27
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>

using namespace std;

    ifstream f("subsir2.in");
    ofstream g("subsir2.out");

    int n,v[5005],l[5005],i,minim,j,lgmaxim,p[5005],maxim,poz;

    void citire(){
        f>>n;
        for(i=1;i<=n;i++)
            f>>v[i];
    }

    void solve(){
        l[n]=1;
        p[n]=-1;
        for(i=n-1;i>=1;i--){
            minim=1000005;
            maxim=0;
            for(j=i+1;j<=n;j++)
                if(v[j]>=v[i] && v[j]<=minim && l[j]>=maxim){
                    minim=v[j];
                    poz=j;
                    maxim=l[j];
                    }

                if(minim==1000005){
                    l[i]=1;
                    p[i]=-1;}
                else{
                    l[i]=maxim+1;
                    p[i]=poz;
                    }
                    if(l[i]>lgmaxim)
                        lgmaxim=l[i];

        }

    }

int main()
{
    citire();
    solve();
    g<<lgmaxim<<'\n';
        for(i=1;i<=n;i++)
            if(l[i]==lgmaxim){
                g<<i<<' ';
                i=p[i];
                break;}

        while(p[i]!=-1){
            g<<i<<' ';
            i=p[i];
        }

        g<<i;

    return 0;
}