Cod sursa(job #1233126)

Utilizator paul_danutDandelion paul_danut Data 24 septembrie 2014 20:19:50
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <queue>
#include <iostream>
using namespace std;

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

int const Nmax=100000;
long int a[Nmax],poz[Nmax],L[Nmax],n,i,j,nr=1;

struct cmp{
   bool operator()(int x,int y) const
            {return L[x]<L[y];}
};
priority_queue<int,vector<int>,cmp> q;
queue<int> save;


int main()
{
    f>>n;
    for(i=1;i<=n;i++)
       f>>a[i];
    f.close();

    L[n]=1;poz[n]=n;q.push(n);

    for(i=n-1;i>=1;i--)
        {
            L[i]=1;poz[i]=i;
            j=q.top();q.pop();
            save.push(j);
            while( a[i] > a[j] && !q.empty())
                  {j=q.top();q.pop();
                  save.push(j);}
            if(a[i] < a[j])
                {L[i]=L[j]+1;
                poz[i]=j;
                q.push(i);}
            while(!save.empty())
            {
                j=save.front();save.pop();
                q.push(j);
            }

        }

    int maxim=-1,k;
    for(i=1;i<=n;i++)
       if(maxim<L[i])
         {maxim=L[i];
         k=i;}
    g<<L[k]<<'\n';

    for(i=1,j=k;i<=L[k];i++,j=poz[j])
       g<<a[j]<<' ';
    g.close();
}