Cod sursa(job #3289086)

Utilizator paull122Paul Ion paull122 Data 25 martie 2025 16:25:12
Problema Subsir 2 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

#define NMAX 5000
#define LOG 17

#define ll long long int
#define BASE 1024

#define MOD 10000


using namespace std;

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


int nxt[NMAX+1];
int a[NMAX+1];
int dp[NMAX+1];
int n;
int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i];
        dp[i] = n+1;
    }
    a[0] = -2e9;
    dp[0] = n+1;
    dp[n]=1;
    for(int i=n;i>=1;i--)
    {
        int mx=0;
        for(int j=i-1;j>=0;j--)
        {
            if(a[j] <= a[i] && (!mx || a[mx]<a[j]))
            {
                mx=j;
                if((dp[j]==dp[i]+1 && a[nxt[j]] > a[i]) || (dp[j]>dp[i]+1))
                {
                    dp[j] = dp[i]+1;
                    nxt[j] = i;
                }
            }
        }
    }
    fout << dp[0]-1 << '\n';
    int j = nxt[0];
    while(j)
    {
        fout << j << " ";
        j = nxt[j];
    }
}