Cod sursa(job #2179556)

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

using namespace std;

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

int n, m, q, f, si, a[N+2], best[N+2], pre[N+2], sol[N+2];

int main()
{
    int i, j;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>a[i];
        best[i]=1;
    }
    for(i=2; i<=n; i++)
        for(j=1; j<=i-1; j++)
            if(a[i]>=a[j])
                if(best[i]<=best[j]+1)
                    best[i]=best[j]+1, pre[i]=j;
    for(i=1; i<=n; i++) m=max(m,best[i]);
    fout<<m<<'\n';
    f=INT_MAX;
    for(i=1; i<=n; i++)
        if(best[i]==m && a[i]<f)
        {
            f=a[i];
            si=i;
        }
    i=si;
    while(i)
    {
        sol[++q]=i;
        i=pre[i];
    }
    for(i=q; i>=1; i--) fout<<sol[i]<<' ';
    return 0;
}