fork download 
  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> a, 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,mp[v[i]],mp[v[i]]) + 1; 
  38.         p = solve(1,mp[v[i]],mp[v[i]]) + 1;
  39.     }
  40.     else {
  41.         if(!t and mp[v[i]] > w) x = solve(t,i+1,mp[v[i]]) + 1; 
  42.         if(t and mp[v[i]] < w) y = solve(t,i+1,mp[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(auto &i : v) cin >> i; 
  52.     for(int i = 0; i < n; i++) mp[v[i]];
  53.     for(auto i : mp) mp[i.first] = nxt++;
  54.     memset(dp,-1,sizeof(dp));
  55.     cout << solve(0,0,0);
  56. }
  57. int Gaza()
  58. {   You_ss_ef   
  59.     IO();
  60.     int TC = 1;
  61.     cin >> TC;
  62.     do {
  63.         answer();
  64.         TC--;
  65.         // if (TC)
  66.             cout el;
  67.     } while (TC != 0);
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 34832KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/4IPY7Y
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!