Cod sursa(job #1016924)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 26 octombrie 2013 21:54:46
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

int a[100010],l[100010],t[100010],i,j;

struct cmp
{
    bool operator()(const int v1,const int v2)
    {
        int vv1=v1,vv2=v2;
        if(a[vv1]<a[i])
        {
            if(a[vv2]<a[i])
            {
                if(l[vv1]>l[vv2])
                    return 0;
                return 1;
            }
            return 0;
        }
        return 1;
    }
};

int main()
{
    priority_queue<int,vector<int>,cmp>q;
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    int n,maxim,imax,lmax=0,lmaxi;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
        q.push(i-1);
        l[i]=l[q.top()]+1;
        t[i]=q.top();
        if(l[i]>lmax)
        {
            lmax=l[i];
            lmaxi=i;
        }
    }
    fout<<lmax<<"\n";
    int p=0;
    for(i=lmaxi;i;i=t[i])
        l[++p]=a[i];
    for(i=p;i>=1;i--)
        fout<<l[i]<<" ";
    return 0;
}