# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
383002 | 2021-03-28T17:18:51 Z | valerikk | Exam (eJOI20_exam) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int N = 5005; bool ok[N][N]; int dp[N][N]; int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = 0; i < n; ++i) { ok[i][i] = true; for (int j = i - 1; j >= 0; --j) { if (a[j] > a[i]) break; ok[j][i] = true; } for (int j = i + 1; j < n; ++j) { if (a[j] > a[i]) break; ok[j][i] = true; } } for (int i = 0; i < n; ++i) { if (ok[0][i] && b[0] == a[i]) { dp[0][i] = 1; } } for (int i = 1; i < n; ++i) { int mx = 0; for (int j = 0; j < n; ++j) { mx = max(mx, dp[i - 1][j]); if (ok[i][j]) { dp[i][j] = mx; if (b[i] == a[j]) ++dp[i][j]; } } } int ans = 0; for (int i = 0; i < n; ++i) ans = max(ans, dp[n - 1][i]); cout << ans << endl; return 0; }