Cod sursa(job #2560549)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 28 februarie 2020 08:49:30
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>

using namespace std;

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

int n, i, j;
int v[5001];
int best[5001], maxim;
bool ok[5001];
int lg, poz, u;
int rez[5001];


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

        maxim = 0;
        for (j=1; j<i; j++)
            if (v[j] <= v[i])
                maxim = max(maxim, best[j]);

        for (j=1; j<i; j++)
            if (best[j] == maxim)
                ok[j] = 1;

        best[i] = maxim + 1;
    }

    lg = n, poz = 0;
    for (i=1; i<=n; i++)
        if (!ok[i] && best[i] < lg)
            lg = best[i], poz = i;
        else if (!ok[i] && best[i] == lg && v[i] < v[poz])
            poz = i;

    v[0] = 1000001;
    g << lg << "\n";
    for (i=1; i<lg; i++)
    {
        poz = 0;
        for (j=u+1; j<=n; j++)
            if (ok[j] && best[j] == i && v[j] < v[poz])
                poz = j;
        g << poz << " ";
        u = poz;
    }

    poz = 0;
    for (j=u+1; j<=n; j++)
        if (!ok[j] && best[j] == lg && v[j] < v[poz])
            poz = j;
    g << poz;

    return 0;
}