Cod sursa(job #3004720)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 16 martie 2023 16:00:52
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <cmath>
#include <queue>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,v[100001],len[100001],ant[100001],lmax,pmax;
priority_queue<pair<int,int>> q;
int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> v[i];

    for(int i=n;i>=1;i--)
    {
        len[i]=1;
        ant[i]=-1;
        if(!q.empty())
        {
            priority_queue<pair<int,int>> q2;
            q2=q;
            while(v[i]>=v[q2.top().second] && !q2.empty())
                q2.pop();
            len[i]=1+q2.top().first;
            ant[i]=q2.top().second;
        }
        q.push(make_pair(len[i],i));
        if(len[i]>lmax)
        {
            lmax=len[i];
            pmax=i;
        }
    }
    fout << lmax << "\n";
    while(pmax!=-1)
    {
        fout << v[pmax] << " ";
        pmax=ant[pmax];
    }
    return 0;
}