Submission #464521

#TimeUsernameProblemLanguageResultExecution timeMemory
464521SamAndExam (eJOI20_exam)C++17
0 / 100
26 ms16092 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 100005, N0 = 5003; int n; int a[N], b[N]; int maxi[N0][N0]; int dp[N0][N0]; bool c[N0][N0]; int rec(int l, int r) { if (l > r) return 0; if (c[l][r]) return dp[l][r]; c[l][r] = true; int m = maxi[l][r]; int dpl = 0; int q = 0; for (int i = m; i >= l; --i) { if (b[i] == a[m]) ++q; dpl = max(dpl, q + rec(l, i - 1)); } int dpr = 0; q = 0; for (int i = m; i <= r; ++i) { if (b[i] == a[m]) ++q; dpr = max(dpr, q + rec(i + 1, r)); } dp[l][r] = dpl + dpr - (b[m] == a[m]); return dp[l][r]; } void solv0() { for (int l = 1; l <= n; ++l) { maxi[l][l] = l; for (int r = l + 1; r <= n; ++r) { maxi[l][r] = maxi[l][r - 1]; if (a[r] > a[maxi[l][r]]) maxi[l][r] = r; } } cout << rec(1, n) << "\n"; } void solv() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> b[i]; if (n <= 5000) { solv0(); return; } } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solv(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...