Cod sursa(job #1043470)

Utilizator western100Sutu Eusebiu western100 Data 28 noiembrie 2013 17:27:02
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int main()
{
    int n,x[100001],lis[1000001],nr[100001],i,j;
    f>>n;
    for(i=1;i<=n;i++) f>>x[i];
    int maxx;
    lis[n]=1;
    int maxx2=1,mixx;
    for(i=n-1;i>=1;i--)
    {
        maxx=0;
        for(j=i+1;j<=n;j++)
        {
            if(x[i]<=x[j]&&lis[j]>maxx) maxx=lis[j];
        }
        lis[i]=maxx+1;
        if(maxx2<lis[i])
        {
            maxx2=lis[i];
            mixx=i;
        }
    }
    g<<maxx2<<'\n';
    nr[n]=1;
    for(i=n-1;i>=1;i--)
    {
        for(j=i+1;j<=n;j++)
        {
            if(lis[j]==lis[i]-1&&x[i]<=x[j])
            {
                nr[i]+=nr[j];
                if(nr[i]==0) nr[i]=1;
            }
        }
    }
    bool ver;
    g<<x[mixx]<<' ';
    for(i=maxx2-1;i>=1;i--)
    {
        ver=1;
        for(j=mixx+1;j<=n&&ver==1;j++)
        {
            if(lis[j]==i&&x[j]>=x[mixx])
            {
                mixx=j;
                ver=0;
                g<<x[mixx]<<' ';
            }
        }
    }
    return 0;
}