Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- //#include <bits/stdc++.h>
- using namespace std;
- int n;
- int ar[100005];
- int ar_2[100005];
- int dp[100005][2];
- int rec(int pos, int side){
- if(pos==n){
- return 0;
- }
- if(dp[pos][side]!= -1){
- return dp[pos][side];
- }
- int result=0;
- if(pos + 1 < n) {
- if(side==0){
- if(ar[pos]<=ar[pos+1]){
- result=max(result, rec(pos+1, 0) + 1) ;
- }
- if(ar[pos]<=ar_2[pos+1]){
- result=max(result, rec(pos+1, 1) + 1);
- }
- }
- if(side==1){
- if(ar_2[pos]<=ar_2[pos+1]){
- result=max(result, rec(pos+1, 1) + 1);
- }
- if(ar_2[pos]<=ar[pos+1]){
- result=max(result, rec(pos+1, 0) + 1);
- }
- }
- }
- return dp[pos][side]=result;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin>>n;
- for(int i=0; i<n; i++){
- cin>>ar[i];
- }
- for(int i=0; i<n; i++){
- cin>>ar_2[i];
- }
- multiset<int>m;
- memset(dp, -1, sizeof dp);
- for(int i=0; i<n; i++){
- for(int j=0; j<2; j++){
- m.insert(rec(i, j) + 1);
- }
- }
- cout<< (*m.rbegin());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement