Cod sursa(job #1533944)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 23 noiembrie 2015 09:18:01
Problema Subsir 2 Scor 49
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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;
        if (b[i] > max1)
            max1 = b[i];
    }
    for (i = 1; i <= max1; i++)
        min1[i] = INF;
    min1[max1+1] = -INF, p1[max1+1] = -1;
    for (i = 1; i <= n; i++)
    {
        //g << b[i] << " ";
        if (min1[b[i]] > a[i] && a[i] > min1[b[i]+1] && p1[b[i]+1] < i)
            min1[b[i]] = a[i], p1[b[i]] = i;
    }
    g << max1 << "\n";
    for (i = max1; i >= 1; i--)
        g << p1[i] << " ";
    return 0;
}