Submission #464548

#TimeUsernameProblemLanguageResultExecution timeMemory
464548SamAndExam (eJOI20_exam)C++17
30 / 100
27 ms24968 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 = 203; int n; int a[N], b[N]; int maxi[N0][N0]; int dp[N0][N0][N0]; bool c[N0][N0][N0]; int rec(int l, int r, int ul, int ur, int p) { if (l > r) return 0; ul = max(ul, l - 1); ur = min(ur, r + 1); if (ul + 1 >= ur) return 0; int m = maxi[l][r]; if (c[m][ul][ur]) return dp[m][ul][ur]; c[m][ul][ur] = true; if (ul < m && m < ur && a[m] == b[m]) dp[m][ul][ur] = rec(l, m - 1, ul, ur, m) + rec(m + 1, r, ul, ur, m) + 1; else dp[m][ul][ur] = rec(l, m - 1, ul, ur, m) + rec(m + 1, r, ul, ur, m); if (p == 0) { return dp[m][ul][ur]; } if (p == l - 1) { int q = 0; for (int i = ul + 1; i <= ur - 1; ++i) { if (b[i] == a[p]) ++q; if (i < m && m < ur && a[m] == b[m]) ++q; dp[m][ul][ur] = max(dp[m][ul][ur], q + rec(l, m - 1, i, ur, m) + rec(m + 1, r, i, ur, m)); if (i < m && m < ur && a[m] == b[m]) --q; } } else if (p == r + 1) { int q = 0; for (int i = ur - 1; i >= ul + 1; --i) { if (b[i] == a[p]) ++q; if (ul < m && m < i && a[m] == b[m]) ++q; dp[m][ul][ur] = max(dp[m][ul][ur], q + rec(l, m - 1, ul, i, m) + rec(m + 1, r, ul, i, m)); if (ul < m && m < i && a[m] == b[m]) --q; } } else assert(false); return dp[m][ul][ur]; } int solv0() { memset(c, false, sizeof c); 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; } } return rec(1, n, 0, n + 1, 0); } int p[N]; int ul[N], ur[N]; int solv2() { for (int i = 1; i <= n; ++i) { p[i] = p[i - 1]; if (a[i] == b[i]) ++p[i]; } ul[0] = 0; for (int i = 1; i <= n; ++i) { if (a[i] > b[i]) { ul[i] = i; } else { ul[i] = ul[i - 1]; } } ur[n + 1] = n + 1; for (int i = n; i >= 1; --i) { if (a[i] > b[i]) { ur[i] = i; } else { ur[i] = ur[i + 1]; } } int ans = 0; for (int i = 1; i <= n; ++i) { if (a[i] <= b[i]) { if (p[ur[i] - 1] - p[ul[i]] > 0) ++ans; } } return ans; } 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) { cout << solv0() << "\n"; return; } bool z2 = true; for (int i = 1; i <= n; ++i) { if (b[i] != b[1]) { z2 = false; break; } } if (z2) { cout << solv2() << "\n"; 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 st = 100; while (st--) { n = rnf() % 100 + 1; for (int i = 1; i <= n; ++i) { a[i] = rnf() % 100 + 1; } b[1] = a[rnf() % n + 1]; for (int i = 2; i <= n; ++i) b[i] = b[1]; if (solv0() != solv2()) { cout << "WA\n"; return 0; } } cout << "OK\n"; return 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...