Advertisement
Josif_tepe

Untitled

Feb 6th, 2024
985
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. //#include <bits/stdc++.h>
  3. #include <fstream>
  4. #include <string>
  5. #include <set>
  6. #include <set>
  7. #define MOD 1000000007
  8. #define ll long long
  9. using namespace std;
  10. int n;
  11. int arr1[100005];
  12. int arr2[100005];
  13. int memo[100005][2];
  14.  
  15. int dp (int at, int where){
  16.     if(at==n){
  17.         return 0;
  18.     }
  19.     if(memo[at][where] != -1) return memo[at][where];
  20.    
  21.     int res=0;
  22.    
  23.     if(where == 0 and at+1<n){
  24.         if(arr1[at+1]>=arr1[at]){
  25.             res = max(res,dp(at+1,0)+1);
  26.         }
  27.        
  28.         if(arr2[at+1]>=arr1[at]){
  29.             res = max(res,dp(at+1,1)+1);
  30.         }
  31.     }
  32.     else if(where == 1 and at+1<n){
  33.         if(arr2[at+1]>=arr2[at]){
  34.             res = max(res,dp(at+1,1)+1);
  35.         }
  36.        
  37.         if(arr1[at+1]>=arr2[at]){
  38.             res=max(res,dp(at+1,0)+1);
  39.         }
  40.     }
  41.    
  42.     return memo[at][where] = res;
  43. }
  44. int main() {
  45.     cin >> n;
  46.     for(int i =0;i<n;i++){
  47.         cin >> arr1[i];
  48.    
  49.     }
  50.     for(int i = 0;i<n;i++){
  51.         cin >> arr2[i];
  52.     }
  53.    
  54.     memset(memo, -1, sizeof memo);
  55.     int res = 0;
  56.     for(int i= 0;i<n;i++){
  57.         res = max(res ,max(dp(i,0), dp(i,1)));
  58.        
  59.     }
  60.     cout << res+1;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement