제출 #468677

#제출 시각아이디문제언어결과실행 시간메모리
468677mychecksedadExam (eJOI20_exam)C++17
0 / 100
7 ms4300 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10, K = 20; #define pb push_back int n, a[N], b[N], rmq[N][K]; map<int, vector<int>> m; int subtask2(){ int ans = 0; vector<bool> is_taken(n + 5, 0); for(int i = 1; i <= n; i++){ if(a[i] == b[1]){ ans++; int l = i-1, r = i + 1; is_taken[i] = 1; for(; l >= 1 && !is_taken[l] && a[l] < b[1]; l--) ans++, is_taken[l] = 1; for(; r <= n && !is_taken[r] && a[r] < b[1]; r++) ans++, is_taken[r] = 1; } } return ans; } int subtask4(){ // map<int, vector<int>> m; // for(int i = 1; i <= n; i++) m[a[i]].pb(i); // auto last_occ = [](int val, int pos){ // return upper_bound(m[val].begin(), m[val].end(), pos) - m[val].begin(); // }; // vector<int> dp(n + 5, 0); // for(int i = 1; i <= n; i++){ // dp[i] = dp[i - 1]; // if(a[i] <= b[i]){ // int s = m[b[i]].size(); // if(s == 0) continue; // int pos = last_occ(b[i], i); // if(pos == 0) continue; // pos--; // dp[i] = max(dp[i], dp[pos - 1] + num_of_occ(b[i], pos, i)); // } // } int ans = 0; //Will be completed. return ans; } void precalc(){ for(int i = 1; i <= n; i++) rmq[i][0] = a[i]; for(int j = 1; j < K; j++){ for(int i = 1; i + (1<<j) <= n + 1; i++){ rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j - 1]); } } } int main(){ cin.tie(0); ios::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> b[i]; precalc(); if(n > 5000){ bool is_b = 1; for(int i = 2; i <= n; i++) if(b[i] != b[i - 1]) is_b = 0; if(is_b){ cout << subtask2(); }else{ cout << subtask4(); } return 0; } vector<vector<int>> occ(n + 2, vector<int>(n+2, 0)); vector<int> dp(n+3); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ occ[i][j] = occ[i][j - 1]; if(a[j] <= b[j] && b[j] == b[i]) occ[i][j]++; } } int ans = 0; for(int i = 1; i <= n; i++){ dp[i] = dp[i - 1]; for(int j = 1; j <= i; j++){ int num = occ[i][i] - occ[i][j - 1]; dp[i] = max(dp[i], dp[j - 1] + num); } ans = max(ans, dp[i]); } cout << ans; 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...