Advertisement
Josif_tepe

Untitled

Apr 4th, 2023
823
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. //#include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. int n;
  7. int ar[100005];
  8. int ar_2[100005];
  9. int dp[100005][2];
  10. int rec(int pos, int side){
  11. if(pos==n){
  12.     return 0;
  13. }
  14. if(dp[pos][side]!= -1){
  15.     return dp[pos][side];
  16. }
  17. int result=0;
  18.     if(pos + 1 < n) {
  19.         if(side==0){
  20.             if(ar[pos]<=ar[pos+1]){
  21.                 result=max(result, rec(pos+1, 0) + 1) ;
  22.             }
  23.             if(ar[pos]<=ar_2[pos+1]){
  24.                 result=max(result, rec(pos+1, 1) + 1);
  25.             }
  26.         }
  27.         if(side==1){
  28.             if(ar_2[pos]<=ar_2[pos+1]){
  29.                 result=max(result, rec(pos+1, 1) + 1);
  30.             }
  31.             if(ar_2[pos]<=ar[pos+1]){
  32.                 result=max(result, rec(pos+1, 0) + 1);
  33.             }
  34.         }
  35.     }
  36. return dp[pos][side]=result;
  37. }
  38. int main()
  39. {
  40.     ios_base::sync_with_stdio(false);
  41.     cin>>n;
  42.     for(int i=0; i<n; i++){
  43.         cin>>ar[i];
  44.     }
  45.     for(int i=0; i<n; i++){
  46.         cin>>ar_2[i];
  47.     }
  48.     multiset<int>m;
  49.     memset(dp, -1, sizeof dp);
  50.     for(int i=0; i<n; i++){
  51.         for(int j=0; j<2; j++){
  52.             m.insert(rec(i, j) + 1);
  53.         }
  54.     }
  55.     cout<< (*m.rbegin());
  56.     return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement