Cod sursa(job #895279)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 februarie 2013 10:48:19
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
using namespace std;

const int NMAX = 100009;
const int DIM = 262144;
int a[NMAX], best[NMAX], n, pre[NMAX], maxim, poz;
char c[DIM + 10], *p;

inline void read_Data();
inline void solve();

int main()
{
    freopen("scmax.in", "rt", stdin); freopen("scmax.out", "wt", stdout);
    read_Data();
    solve();

    printf("%d\n", maxim);
    for(int i = poz; i <= n; i = pre[i])
        printf("%d ", a[i]);

    printf("\n");
    return 0;
}

inline void read_Data()
{
    scanf("%d", &n);
    fread(c, 1, DIM, stdin);
    int nbr, k = 0;
    for(p = c + 1; *p; )
        if(*p != ' ' && *p != '\n')
        {
            nbr = 0;
            while(*p >= '0' && *p <= '9')
            {
                nbr = nbr * 10 + *p - '0';
                ++p;
            }
            a[++k] = nbr;
        }
        else
            ++p;
}

inline void solve()
{
    best[n] = 1;
    pre[n] = n + 1;
    for(int i = n; i > 1; --i)
        for(int j = i - 1; j >= 1; --j)
            if(a[j] < a[i] && best[j] <= best[i])
            {
                best[j] = 1 + best[i];
                if(best[j] > maxim) maxim = best[j], poz = j;
                pre[j] = i;
            }
}