fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <string>
  7. #define You_ss_ef ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  8. #define pi 3.141592654
  9. #define tc int T; cin >> T; while (T--)
  10. #define FP(_) fixed << std::setprecision(_)
  11. #define Gaza main
  12. #define ll long long
  13. #define ld long double
  14. #define ss << ' '
  15. #define el << '\n'
  16. #define all(_) _.begin(), _.end()
  17. #define rall(_) _.rbegin(), _.rend()
  18. #define uni(_) _.erase(unique(all(_)), _.end())
  19. using namespace std;
  20. void IO() {
  21. #ifndef ONLINE_JUDGE
  22. freopen("input.txt", "r", stdin);
  23. freopen("output.txt", "w", stdout);
  24. #endif
  25. } 
  26. int n;   
  27. vector <int> v;
  28. int dp[2][2001][2001];
  29. int solve(int t, int i, int w)
  30. {
  31.     if(i == n) return 0;
  32.     int &ret = dp[t][i][w];
  33.     if(~ret) return ret; 
  34.     int x = 0, y = 0, z = 0, o = 0, p = 0; 
  35.     if(w == 0) {
  36.         o = solve(0,v[i],v[i]) + 1; 
  37.         p = solve(1,v[i],v[i]) + 1;
  38.     }
  39.     else {
  40.         if(!t and v[i] > w) x = solve(t,i+1,v[i]) + 1; 
  41.         if(t and v[i] < w) y = solve(t,i+1,v[i]) + 1;
  42.     }
  43.     z = solve(t,i+1,w);
  44.     return ret = max({x,y,z,o,p});
  45. }
  46. void answer() 
  47. {   
  48.     cin >> n;
  49.     v.resize(n);
  50.     for(auto &i : v) cin >> i; 
  51.     memset(dp,-1,sizeof(dp));
  52.     cout << solve(0,0,0);
  53. }
  54. int Gaza()
  55. {   You_ss_ef   
  56.     IO();
  57.     int TC = 1;
  58.     cin >> TC;
  59.     do {
  60.         answer();
  61.         TC--;
  62.         // if (TC)
  63.             cout el;
  64.     } while (TC != 0);
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 34924KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QoZ3QF
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!