Untitled
unknown
c_cpp
a year ago
984 B
3
Indexable
// #define Many_SubTask #include <bits/stdc++.h> using namespace std; #define int long long #define all(a) begin(a), end(a) #define pb push_back #define pii pair<int, int> #define F first #define S second #define mp make_pair const int mod = 998244353; const int inf = 1e18; const int MAXN = 1000005; int dp[2][MAXN]; int a[MAXN], c[MAXN]; void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i] == c[j]) { dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + 1; } else { dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i) & 1][j - 1]); } } } cout << dp[n & 1][m] << '\n'; } signed main() { cin.sync_with_stdio(0), cin.tie(0); int N = 1; #ifdef Many_SubTask cin >> N; #endif for (int i = 1; i <= N; i++) { solve(); } }
Editor is loading...
Leave a Comment