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, nxt = 1;   
  27. vector <int> v;
  28. int dp[2][2001][2005];
  29. map <int,int> mp;
  30. int solve(int t, int i, int w)
  31. {
  32.     if(i == n) return 0;
  33.     int &ret = dp[t][i][w];
  34.     if(~ret) return ret; 
  35.     int x = 0, y = 0, z = 0, o = 0, p = 0; 
  36.     if(w == 0) {
  37.         o = solve(0,i+1,v[i]) + 1; 
  38.         p = solve(1,i+1,v[i]) + 1;
  39.     }
  40.     else {
  41.         if(!t and v[i] > w) x = solve(t,i+1,v[i]) + 1; 
  42.         if(t and v[i] < w) y = solve(t,i+1,v[i]) + 1;
  43.     }
  44.     z = solve(t,i+1,w);
  45.     return ret = max({x,y,z,o,p});
  46. }
  47. void answer() 
  48. {   
  49.     cin >> n;
  50.     v = vector <int> (n);
  51.     for(int i = 0; i < n; i++) cin >> v[i]; 
  52.     for(int i = 0; i < n; i++) mp[v[i]];
  53.     for(auto &[i,j] : mp) j = nxt++;
  54.     for(int i = 0; i < n; i++) v[i] = mp[v[i]];
  55.     memset(dp,-1,sizeof(dp));
  56.     cout << solve(0,0,0);
  57.     mp.clear();
  58. }
  59. int Gaza()
  60. {   You_ss_ef   
  61.     IO();
  62.     int TC = 1;
  63.     cin >> TC;
  64.     do {
  65.         answer();
  66.         TC--;
  67.         // if (TC)
  68.             cout el;
  69.     } while (TC != 0);
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 34780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0NRoj6
language:
C++14 (gcc 8.3)
created:
2 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!