Cod sursa(job #3287701)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 18 martie 2025 21:44:19
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
// OJI 2025 11-12 Ivan Andrei
// Aventura 19 Subtask 2
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
  
#pragma GCC optimize("O3") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("avx2") 
  
using namespace std; 
using namespace __gnu_pbds; 
  
#define ordered_set tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> 
#define lsb(x) (x & (-x)) 
  
const long long mod = 1e9 + 7, max_size = 5e3 + 20, INF = 2e9 + 2; 

long long v[max_size], dp[max_size], nxt[max_size];

void solve() 
{
    long long n;
    cin >> n;
    for (long long i = 1; i <= n; i++)
    {
        cin >> v[i];
        dp[i] = INF;
        nxt[i] = n + 1;
    }
    v[0] = -INF;
    dp[0] = INF;
    long long mx = 0;
    for (long long i = n; i >= 0; i--)
    {
        long long mn = INF + 20;
        for (long long j = i + 1; j <= n; j++)
        {
            if (v[j] <= v[i])
            {
                continue;
            }
            if (v[j] < mn)
            {
                if (dp[j] + 1 < dp[i])
                {
                    nxt[i] = j;
                    dp[i] = dp[j] + 1;
                }
                mn = v[j];
            }
        }
        dp[i] = dp[nxt[i]] + 1;
    }
    cout << dp[0] - 1 << '\n';
    int pos = nxt[0];
    while (pos != n + 1)
    {
        cout << pos << " ";
        pos = nxt[pos];
    }
    cout << '\n';
}
  
signed main() 
{ 
#ifdef LOCAL 
    freopen("test.in", "r", stdin); 
    freopen("test.out", "w", stdout); 
#else 
    freopen("subsir2.in", "r", stdin); 
    freopen("subsir2.out", "w", stdout); 
#endif // LOCAL 
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0); 
    long long tt; 
    //cin >> tt; 
    tt = 1; 
    while (tt--) 
    { 
        solve(); 
    } 
    return 0; 
}