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 <vector <ll>> dp, dpp;
  28. vector <ll> v; 
  29. ll solve(int i, int last)
  30. {
  31.     if(i > n) return 0;
  32.     ll &ret = dp[i][last];
  33.     if(~ret) return ret; 
  34.     ll leave = solve(i+1, last);
  35.     ll take = 0;
  36.     if(v[i] >= v[last]) take = solve(i+1, i) + 1;
  37.     return ret = max(take, leave);
  38. }
  39. ll solve1(int i, int last) 
  40. {
  41.     if(i > n) return 0;
  42.     ll &ret = dpp[i][last];
  43.     if(~ret) return ret; 
  44.     ll leave = solve1(i+1, last);
  45.     ll take = 0;
  46.     if(v[i] <= v[last]) take = solve1(i+1, i) + 1;
  47.     return ret = max(take, leave);
  48. }
  49. void answer() 
  50. {   
  51.     cin >> n; 
  52.     v = vector <ll> (n+1);
  53.     for(int i = 1; i <= n; i++) cin >> v[i];
  54.     dpp = dp = vector <vector <ll>> (n+1, vector <ll> (n+1,-1));
  55.     ll ans = 0; 
  56.     for(int i = 1; i <= n; i++) {
  57.         ans = max(ans, solve(1,i) + solve1(1,i) - 1);
  58.     }
  59.     cout << ans; 
  60. }
  61. int Gaza()
  62. {   You_ss_ef   
  63.     IO();
  64.     int TC = 1;
  65.     cin >> TC;
  66.     do {
  67.         answer();
  68.         TC--;
  69.         // if (TC)
  70.             cout el;
  71.     } while (TC != 0);
  72.     return 0;
  73. }
  74.  
  75.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Xe6bgU
language:
C++14 (gcc 8.3)
created:
9 days 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!