Cod sursa(job #2576682)

Utilizator blotucosmincosmin blotucosmin Data 6 martie 2020 21:41:16
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <queue>

using namespace std;

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

int v[100001], lg[100001], maxx, n, p, i, j;
int main()
{
    f >> n;

    for(i = 1; i <= n; ++ i)
        f >> v[i];

    lg[n] = 1;
    for(i = n - 1; i >= 1; i --)
    {
        maxx = 0;
        for(j = i + 1; j <= n; ++ j)
            if(v[i] < v[j] && lg[j] > maxx)
                maxx = lg[j];
        lg[i] = maxx + 1;
    }

    for(i = 1, maxx = 0; i <= n; ++ i)
        if(lg[i] > maxx)
        {
            maxx = lg[i];
            p = i;
        }

    g << maxx << "\n" << v[p] << " ";
    for(i = p + 1; i <= n; ++ i)
        if(v[i] > v[p] && lg[i] == maxx - 1)
        {
            g << v[i] << " ";
            maxx --;
        }
    return 0;
}