Submission #464533

#TimeUsernameProblemLanguageResultExecution timeMemory
464533SamAndExam (eJOI20_exam)C++17
12 / 100
30 ms16264 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]; } int solv0() { for (int l = 1; l <= n; ++l) { for (int r = l; r <= n; ++r) { c[l][r] = false; } } 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); } 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...