Cod sursa(job #2560537)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 28 februarie 2020 08:42:38
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 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, lg1, poz;
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;

    lg1 = lg;
    while (lg)
    {
        rez[lg] = poz;
        lg--;
        for (i=poz-1; i; i--)
            if (best[i] == lg && v[i] < v[poz])
                poz = i;
    }

    g << lg1 << "\n";
    for (i=1; i<=lg1; i++)
        g << rez[i] << " ";

    return 0;
}