Cod sursa(job #2763801)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 16 iulie 2021 20:13:53
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
#define ll long long
#define nl '\n'
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define F0R(i, a, b) for (int i = a; i >= b; --i)
#define FORd(i, n) for (int i = 0; i < n; ++i)
#define F0Rd(i, n) for (int i = n - 1; i >= 0; --i)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 5e3 + 5;

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

void solve() {
    int N, a[mxN], dp[mxN], fiu[mxN];
    fin >> N;
    for (int i = 1; i <= N; ++i) {
        fin >> a[i];
        dp[i] = 1;
        fiu[i] = 0;
    }
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) {
                if (dp[i] <= dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    fiu[i] = j;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        if (dp[ans] <= dp[i]) {
            ans = i;
        }
    }
    fout << dp[ans] << nl;
    stack<int> rez;
    while (ans != 0) {
        rez.push(ans);
        ans = fiu[ans];
    }
    while (rez.size()) {
        fout << rez.top() << " ";
        rez.pop();
    }
}

int main() {
    fin.tie(0); fout.tie(0);
    ios::sync_with_stdio(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

//read the question correctly (ll vs int)
//what's the meaning of the problem ? Think outside the BOX !!!
//edge cases ?
//make it simple
//write everything (observations, edge cases, ideas, steps, methods, ...)