Cod sursa(job #1533950)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 23 noiembrie 2015 09:26:05
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#define INF (1 << 30)

using namespace std;

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

int n, a[5001], b[5001], min1[5001], p1[5001];
int i, j, max1;

int main()
{
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];
    for (i = n; i >= 1; i--)
    {
        max1 = 0;
        for (j = i+1; j <= n; j++)
            if (a[j] > a[i] && max1 < b[j])
                max1 = b[j];
        b[i] = max1+1;
    }
    for (i = 1; i <= n; i++)
        if (b[i] > max1)
            max1 = b[i];
    g << max1 << "\n";

    for (i = 1; i <= max1; i++)
        min1[i] = INF;
    min1[max1+1] = -INF, p1[max1+1] = -1;

    for (j = max1; j >= 1; j--)
    {
        for (i = 1; i <= n; i++)
        {
            if (min1[j] > a[i] && i > p1[j+1] && min1[j+1] < a[i])
                min1[j] = a[i], p1[j] = i;
        }
    }
    for (i = max1; i >= 1; i--)
        g << p1[i] << " ";
    return 0;
}