Cod sursa(job #3241864)

Utilizator AswVwsACamburu Luca AswVwsA Data 5 septembrie 2024 12:50:35
Problema Subsir 2 Scor 73
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#define ll long long
using namespace std;

const int NMAX = 5000;

int d[NMAX + 1];
int v[NMAX + 1];
int urm[NMAX + 1];

ifstream cin("subsir2.in");
ofstream cout("subsir2.out");

void sol(int poz)
{
    if (poz == 0)
        return ;
    sol(urm[poz]);
    cout << poz << " ";
}

signed main()
{
    int n, i, j;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> v[i];
    for (i = 1; i <= n; i++)
    {
        int mn = n + 3;
        int mx = -1e7;
        for (j = i - 1; j >= 1; j--)
            if (v[j] <= v[i] and v[j] > mx)
            {
                mx = max(mx, v[j]);
                if (mn >= 1 + d[j])
                {
                    mn = 1 + d[j];
                    if (urm[i] == 0 or (v[j] <= v[urm[i]]))
                        urm[i] = j;
                }
            }
        if (mn == n + 3)
        {
            mn = 1;
        }
        d[i] = mn;
    }
    int mx = -1e7;
    int ans = n + 3;
    int unde = 0;
    for (i = n; i >= 1; i--)
        if (v[i] > mx)
        {
            if (ans >= d[i])
            {
                ans = d[i];
                if (unde == 0 or (v[unde] >= v[i]))
                    unde = i;
            }
            mx = v[i];
        }
    cout << ans << "\n";
    sol(unde);
}