Advertisement
Josif_tepe

Untitled

Jul 31st, 2023
1,070
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <stack>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 1e5 + 10;
  10. int n;
  11. int a[maxn], b[maxn];
  12. int L[maxn], R[maxn];
  13. void solve_subtask2() {
  14.     int x = b[0];
  15.     int res = 0;
  16.     for(int i = 0; i < n; i++) {
  17.         if(a[i] == x) {
  18.             res++;
  19.             int j = i - 1;
  20.             while(j >= 0 and a[j] <= x) {
  21.                 j--;
  22.                 res++;
  23.             }
  24.             j = i + 1;
  25.             while(j < n and a[j] <= x) {
  26.                 res++;
  27.                 j++;
  28.             }
  29.             i = j - 1;
  30.         }
  31.     }
  32.     cout << res << endl;
  33. }
  34. int dp[5005][5005];
  35. int rec(int i, int j) {
  36.     if(i < 0 or j < 0) {
  37.         return 0;
  38.     }
  39.     if(dp[i][j] != -1) {
  40.         return dp[i][j];
  41.     }
  42.     int res = 0;
  43.     if(a[i] == b[j] and L[i] < j and R[i] > j) {
  44.         res = max(res, rec(i, j - 1) + 1);
  45.     }
  46.     res = max(res, rec(i - 1, j));
  47.     res = max(res, rec(i, j - 1));
  48.     return dp[i][j] = res;
  49. }
  50. int main() {
  51.     ios_base::sync_with_stdio(false);
  52.     cin >> n;
  53.     set<int> st;
  54.     for(int i = 0; i < n; i++) {
  55.         cin >> a[i];
  56.     }
  57.     for(int i = 0; i < n; i++) {
  58.         cin >> b[i];
  59.         st.insert(b[i]);
  60.     }
  61.    
  62.     if((int) st.size() == 1) {
  63.         solve_subtask2();
  64.         return 0;
  65.     }
  66.     else if(n <= 5005){
  67.         for(int i = 0; i < n; i++) {
  68.             int idx1 = -1;
  69.             for(int j = 0; j < i; j++) {
  70.                 if(a[i] < a[j]) {
  71.                     idx1 = j;
  72.                 }
  73.             }
  74.             int idx2 = n;
  75.             for(int j = i + 1; j < n; j++) {
  76.                 if(a[i] < a[j]) {
  77.                     idx2 = j;
  78.                     break;
  79.                 }
  80.             }
  81.             L[i] = idx1;
  82.             R[i] = idx2;
  83.         }
  84.         memset(dp, -1, sizeof dp);
  85.         cout << rec(n - 1, n - 1) << endl;
  86.     }
  87.    
  88.     return 0;
  89. }
  90.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement