Cod sursa(job #3277294)

Utilizator anon2718281828Iasmina Matei anon2718281828 Data 15 februarie 2025 17:21:31
Problema Cel mai lung subsir comun Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("cmlsc.in");
ofstream out("cmlsc.out");

int main() {
    short n, m;
    in >> n >> m;

    vector<short> a(n); for (auto& i: a) in >> i;
    vector<short> b(m); for (auto& i: b) in >> i;

    vector<vector<vector<short>>> dp(n + 1, vector<vector<short>>(m + 1));
    for (short i = 1; i <= n; i++) {
        for (short j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
                dp[i][j].push_back(a[i - 1]);
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], [](const vector<short>& x, const vector<short>& y) {
                    return x.size() < y.size();
                });
            }
        }
    }

    out << dp[n][m].size() << "\n";
    for (const auto& i: dp[n][m]) out << i << " ";

    return 0;
}