Cod sursa(job #2517159)

Utilizator leru007Leru Ursu leru007 Data 2 ianuarie 2020 22:36:15
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pb push_back
#define f first
#define sc second

using namespace std;
ll mod=1e9+7,i,j;
ll a[2000],b[2000],dp[2000][2000];
ll n,m;
int main(){
    ifstream fin("cmlsc.in");
    ofstream fout("cmlsc.out");
    fin>>n>>m;
    for(i=1;i<=n;i++) fin>>a[i];
    for(i=1;i<=m;i++) fin>>b[i];
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i]==b[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }

    vector<ll>ans;
    for(i=n,j=m;i;){
        if(a[i]==b[j]){
            ans.pb(a[i]);
            i--;
            j--;
        }
        else{
            if(dp[i-1][j]>dp[i][j-1]) i--;
            else j--;
        }
    }
    fout<<ans.size()<<"\n";
    reverse(ans.begin(),ans.end());
    for(unsigned ll k=0;k<ans.size();k++) fout<<ans[k]<<" ";
    return 0;
}