Cod sursa(job #1649297)

Utilizator BovisioNitica Ionut Bogdan Bovisio Data 11 martie 2016 13:09:22
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#define dimax 100000

using namespace std;

int n,v[dimax],best[dimax];

void citire()
{
    FILE *f=fopen("scmax.in","r");
    fscanf(f,"%i",&n);
    for(int x=1;x<=n;x++)
        fscanf(f,"%i",&v[x]);
}

void scriere()
{
    FILE *g=fopen("scmax.out","w");
    int solutie[dimax],q=0,y,j=0,M,x;
    M=0;
    for(x=1;x<=n;x++)
        if(best[x]>M)
            M=best[x];
      for(x=1;x<=n;x++)
        if(best[x]==M)
        break;
        solutie[0]=v[x];
        for(y=x-1;y>0;y--)
            if(best[y]+1==best[x]-j)
            {
                solutie[++q]=v[y];
                j++;
            }
        fprintf(g,"%i\n",M);
        for(x=q;x>=0;x--)
           fprintf(g,"%i ",solutie[x]);
        fprintf(g,"\n");
}
int main()
{
    int maxim,y;
    citire();
    best[1]=1;
    for(int x=2;x<=n;x++)
    {
        y=0;
        maxim=0;
        while(x-y>=0)
        {
            while((x-++y>=0)&&(v[x-y]>v[x]));
            if(x-y==-1)
                best[x]=1;
            else
                if(maxim<best[x-y])
                     maxim=best[x-y];
        }
        best[x]=maxim+1;
    }
    scriere();
    return 0;
}