Cod sursa(job #3242634)

Utilizator xiaolaobanCorman Denis xiaolaoban Data 12 septembrie 2024 21:06:44
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

#define pb push_back 

int main() 
  {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("cmlsc.in", "r", stdin);
    freopen("cmlsc.out", "w", stdout);
    int n, m; cin>>n>>m;
    vi a(n); vi b(m);
    int dp[1028][1028];
    for(int i = 1; i <= n; i++)
      cin>>a[i];
    for(int j = 1; j <= m; j++)
      cin>>b[j];
    for(int i = 1; i <= n; i++)
      {
      for(int j = 1; j <= m; j++)
        {
          if(a[i] == b[j])
              dp[i][j] = 1+ dp[i-1][j-1];
          else 
            dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
        }
      }
    cout<<dp[n][m]<<'\n';
    int i = n; int j = m;
    vi v;
    while(i > 0 && j > 0)
      {
        if(a[i] ==  b[j])
          {
            v.pb(a[i]);
            i--;
            j--;
          }
        else if(dp[i-1][j] > dp[i][j-1])
          i--;
        else
          j--;
      }
    sort(v.rbegin(), v.rend());
    for(auto it : v)
      cout<<it<<" ";

  }