Cod sursa(job #2180374)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 20 martie 2018 20:30:00
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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;
    bool ok;
    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++)
    {
        ok=1;
        for(j=1; j<=i-1; j++)
            if(a[j]<=a[i])
            {
                ok=0;
                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]);
            }
        if(ok)
        {
            best[i]=1;
            if(a[i]<a[minlex[1]]) minlex[1]=i;
        }
    }
    fout<<m<<'\n';
    for(i=1; i<=m; i++) fout<<minlex[i]<<' ';
    return 0;
}