Cod sursa(job #2780140)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 6 octombrie 2021 09:49:05
Problema Subsir 2 Scor 42
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
#define N 5005
#define INF 1000000000
int n, minn, poz, val, a[N], tail[N], nex[N];
int main() {
    fin >> n;
    for (int i=1;i<=n;i++){
        fin >> a[i];
    }

    tail[n] = 1;
    for (int i=n-1;i>=1;i--){
        minn = INF;
        poz = n + 1;
        val = INF;
        for (int j=i+1;j<=n;j++){
            if (minn > tail[j] && a[i] <= a[j] && a[j] < val){
                minn = tail[j];
                poz = j;
                val = a[j];

            }
        }
        if (poz <= n){
            tail[i] = minn + 1;
            nex[i] = poz;
        }else{
            tail[i] = 1;
        }
    }
    minn = tail[1];
    poz = 1;
    for (int i=2;i<=n;i++){
        if (minn < tail[i]){
            minn = tail[i];
            poz = i;
        }
    }
    fout << minn << '\n';

   /* for (int i=1;i<=n;i++){
        fout << tail[i] << ' ';
    }
    fout << '\n';

    for (int i=1;i<=n;i++){
        fout << nex[i] << ' ';
    }
    fout << '\n';*/
    while(nex[poz] != poz){
        fout << poz << ' ';
        poz = nex[poz];
    }
    return 0;
}