Cod sursa(job #2892936)

Utilizator PushkinPetolea Cosmin Pushkin Data 24 aprilie 2022 00:23:32
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>
using namespace std;
int **d;

void read_input(vector<int> &a, vector<int> &b, string filename_in) {
    ifstream in(filename_in);

    size_t len;

    in >> len;
    a.resize(len);
    in >> len;
    b.resize(len);

    for(size_t i = 0; i < a.size(); i++)
        in >> a[i];

    for(size_t i = 0; i < b.size(); i++)
        in >> b[i];

    in.close();
}

vector<int> solve_dp(vector<int> &a, vector<int> &b) {
    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));

    // Compute DP Array
    for(size_t i = 0; i < a.size(); i++)
        for(size_t j = 0; j < b.size(); j++) {
            if(a[i] == b[j])
                dp[i + 1][j + 1] = dp[i][j] + 1;
            else
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        }

    // Get length of maximum subset
    int max_len = dp.back().back();

    vector<int> res(max_len);
    size_t res_pos = res.size();

    // Get subset
    int i = a.size() - 1;
    int j = b.size() - 1;
    while(i >= 0 && j >= 0) {
        if(a[i] == b[j]) {
            res[--res_pos] = a[i];
            i--;
            j--;
        } else if(dp[i + 1][j] > dp[i][j + 1]) {
            j--;
        } else {
            i--;
        }
    }

    return res;
}

void write_output(vector<int> &res, string filename_out) {
    ofstream out(filename_out);

    out << res.size() << '\n';
    for(int x : res)
        out << x << ' ';

    out.close();
}

int main() {
    vector<int> a, b;
    read_input(a, b, "cmlsc.in");

    vector<int> res = solve_dp(a, b);

    write_output(res, "cmlsc.out");

    return 0;
}