Advertisement
Zeinab_Hamdy

Untitled

Jul 29th, 2023
928
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define nl "\n"
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define ll long long
  8. #define ull unsigned ll
  9. #define RV  return void
  10. #define inf 2000000000
  11. //#define MOD ((ll) 1e9 + 7)
  12. #define sz(x) int(x.size())
  13. #define all(v) v.begin(), v.end()
  14. #define rall(v) v.rbegin(), v.rend()
  15. #define Mini(x) *min_element(all(x))
  16. #define Maxi(x) *max_element(all(x))
  17. #define fixed(n) fixed << setprecision(n)
  18. //#define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
  19. #define cin(v) for (auto&i:v) cin >> i;
  20. #define cout(v) for (auto&i:v) cout << i << " ";
  21. #define clr(memo, x) memset(memo, x, sizeof memo)
  22. #define updmin(a, b) a = min(a, b)
  23. #define updmax(a, b) a = max(a, b)
  24. #define vi vector < int >
  25. #define vl vector < ll >
  26. #define vc vector < char >
  27. #define vs vector < string >
  28. #define v2i vector < vector < int > >
  29. #define v2l vector < vector < int > >
  30. #define seti set < int >
  31. #define setl set < ll >
  32. #define mapii map < int , int >
  33. #define mapll map < ll , ll >
  34. #define mapli map < ll , int >
  35. #define mapci map < char , int >
  36. #define mapsi map < string , int >
  37. #define pll pair < ll , ll >
  38. #define pii pair < int , int >
  39. #define range(l,r,x) for(int i=l ; i < r ; i+=x)
  40. #define FastCode ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  41. vector < string > ternary= {"NO\n" , "YES\n"};
  42.  
  43. void  Zainab(){
  44.             #ifndef ONLINE_JUDGE
  45.               freopen("input.txt", "r", stdin);
  46.               freopen("output.txt", "w", stdout);
  47.             #endif
  48. }
  49.  
  50.  
  51. /*================================  Prblem solution  ================================ */
  52.  
  53.  
  54.  
  55. int n ;
  56.  
  57. vector < ll > v , dp ;
  58. deque < ll > dq ;
  59.  
  60. ll rec(int idx  ){
  61.     if( idx >= n or !is_sorted(all(dq)) ) return 0;
  62.  
  63.     ll& ret = dp[idx];
  64.     if(~ret) return ret;
  65.     ret = max(ret , rec(idx+1));
  66.  
  67.     dq.push_back( v[idx] );
  68.     ret = max(ret ,1+ rec(idx+1) );
  69.     dq.pop_back() ;
  70.  
  71.     dq.push_front( v[idx] );
  72.     ret = max(ret ,1+ rec(idx+1) );
  73.     dq.pop_front();
  74.  
  75.     return ret ;
  76. }
  77.  
  78.  
  79.  
  80. void myCode(int test){
  81.  
  82. cin >> n ;
  83.  
  84. v.assign(n,0);
  85. cin(v);
  86.  
  87. dq.clear();
  88. dp.assign(n+1 , -1);
  89.  
  90. cout << rec(0) << nl;
  91.  
  92.  
  93. }
  94.  
  95.  
  96. int main(){
  97.                                    FastCode ;
  98.                                   //   Zainab() ;
  99.  
  100.  
  101.     int testCase=1;
  102.          cin >> testCase ;
  103.       for(int i=1 ; i<= testCase ; i++)
  104.         myCode(i);
  105.  
  106.     return 0;
  107. }
  108.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement