Cod sursa(job #2180369)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 20 martie 2018 20:26:02
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>
#define N 5000

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int n, m, a[N+2], best[N+2], minlex[N+2], sol[N+2];

int main()
{
    int i, j;
    fin>>n;
    a[n+1]=1000001;
    for(i=1; i<=n; i++)
    {
        fin>>a[i];
        minlex[i]=n+1;
    }
    best[1]=1, minlex[1]=1;
    for(i=2; i<=n; i++)
        for(j=1; j<=i-1; j++)
            if(a[j]<=a[i])
            {
                best[i]=max(best[i],best[j]+1);
                if(a[i]<a[minlex[best[j]+1]]) minlex[best[j]+1]=i;
                m=max(m,best[i]);
            }
    fout<<m<<'\n';
    for(i=1; i<=m; i++) fout<<minlex[i]<<' ';
    return 0;
}