Cod sursa(job #1684562)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 11 aprilie 2016 10:04:53
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");
int H[10005],best[1005],nr[1005],i,N,indice[1005],maxim,c,p,rez[1005];
int detbest(int nod)
{
    if(nod>H[0])
        return 0;
    if(nr[H[nod]]<nr[i])
        return H[nod];
    if(2*nod<=N&&2*nod+1<=N)
    {
            int a,b;
            a=detbest(2*nod);
            b=detbest(2*nod+1);
            if(best[a]>best[b])
                return a;
            return b;
    }
    if(2*nod<=N)
        return detbest(2*nod);
    return 0;
}
int main()
{
    fscanf(f,"%d",&N);
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%d",&nr[i]);
        indice[i]=detbest(1);
        best[i]=best[indice[i]]+1;
        if(best[i]>best[maxim])
            maxim=i;
        H[++H[0]]=i;
        c=H[0];
        p=c/2;
        while(best[H[p]]<best[H[c]]&&p>0)
            {swap(H[c],H[p]);c=p;p=c/2;}
        p=c;
        while(1)
        {
            c=2*p;
            if(c>H[0])
                break;
            if(best[H[c+1]]>best[H[c]]&&c+1<=H[0])
                c=c+1;
            if(best[H[c]]<best[H[p]])
                break;
            swap(H[p],H[c]);
            p=c;
        }
    }
    fprintf(g,"%d\n",best[maxim]);
    while(maxim!=0)
    {
        rez[++rez[0]]=maxim;
        maxim=indice[maxim];
    }
    for(i=rez[0];i>0;i--)
        fprintf(g,"%d ",nr[rez[i]]);
    fclose(f);
    fclose(g);
    return 0;
}