Cod sursa(job #3360411)

Utilizator NumberzAndStuffMihail Grecu NumberzAndStuff Data 13 iulie 2026 15:16:23
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#pragma GCC target("popcnt")
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define db long double

const ll INF = 1e18;
const ll MOD = 1e9+7;
const int lg = 31;
const ll inv2 = 500000004;
ll add(ll a, ll b, ll MD = MOD) {return (a+b)%MD;}
ll mns(ll a, ll b, ll MD = MOD) {return add((a-b)%MD, MD);}
ll mult(ll a, ll b, ll MD = MOD) {return ((a%MD) * (b%MD)) % MD;}

ll expo(ll a, ll e = MOD - 2, ll MD = MOD) {
    ll r = 1;
    while (e) {
        if (e & 1) r = mult(r, a, MD);
        a = mult(a, a, MD);
        e >>= 1;
    }
    return r;
}

//stolen
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() ^ random_device{}());

template<class T>
using OSET = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//-------------------------------------------------------------------------------------

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

int dp[1025][1025];
int a[1025], b[1025];
pair<int, int> par[1025][1025];

void solve() {
{

    int n, m;
    ccin >> n >> m;
    for (int i = 1; i <= n; i++) ccin >> a[i];
    for (int i = 1; i <= m; i++) ccin >> b[i];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        dp[i][j] = dp[i-1][j];
        par[i][j] = {i-1, j};
        if (dp[i][j-1] > dp[i][j]) {
            dp[i][j] = dp[i][j-1];
            par[i][j] = {i, j-1};
        }
        if (dp[i-1][j-1] + (a[i] == b[j]) > dp[i][j]) {
            dp[i][j] = dp[i-1][j-1] + (a[i] == b[j]);
            par[i][j] = {i-1, j-1};
        }
    }

    vll ans;
    ll x = n, y = m;
    while (x > 0 && y > 0) {
        ll i = par[x][y].first, j = par[x][y].second;
        if (dp[x][y] > dp[i][j]) ans.push_back(a[x]);
        x = i, y = j;
    }
    ccout << ans.size() << '\n';
    reverse(ans.begin(), ans.end());
    for (ll x : ans) ccout << x << ' ';

}}

int main() {
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(std::ios::fixed); cout.precision(17);

	int tt = 1;
    //cin >> tt;
    while (tt--) solve();

	return 0;
}}