Pagini recente » Cod sursa (job #2953894) | Cod sursa (job #618430) | Cod sursa (job #3174092) | Cod sursa (job #2756112) | Cod sursa (job #3287705)
#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;
v[n + 1] = 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 + 1; 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];
}
}
}
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;
}