fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2023
  3.  
  4. #include<bits/stdc++.h>
  5. //#include <ext/pb_ds/assoc_container.hpp>
  6. //#include <ext/pb_ds/trie_policy.hpp>
  7. //#include <ext/rope>
  8.  
  9. //#pragma GCC optimize("Ofast")
  10. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  11. //#pragma GCC target("avx,avx2,fma")
  12.  
  13. //using namespace std;
  14. //using namespace __gnu_pbds;
  15. //using namespace __gnu_cxx;
  16.  
  17. #define fi first
  18. #define se second
  19. #define TASK "test"
  20. #define pb push_back
  21. #define EL cout << endl
  22. #define Ti20_ntson int main()
  23. #define in(x) cout << x << endl
  24. #define all(x) (x).begin(),(x).end()
  25. #define getbit(x, i) (((x) >> (i)) & 1)
  26. #define cntbit(x) __builtin_popcount(x)
  27. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  28. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  29. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef vector<int> vi;
  35. typedef pair<int,int> vii;
  36. typedef unsigned long long ull;
  37. typedef vector<vector<int>> vvi;
  38. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  39.  
  40. const int N = 5005;
  41. const int oo = INT_MAX;
  42. const int mod = 1e9 + 7;
  43. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  44. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  45.  
  46. int n, dp[N][2], cnt[N], Val[N][N], a[N];
  47. vector<int> Store[N];
  48.  
  49. inline void Read_Input() {
  50.     cin >> n;
  51.     FOR(i, 1, n) {
  52.         int u; cin >> u;
  53.         a[i] = u;
  54.         if (Store[u].size() == 0) Store[u].push_back(0);
  55.         Store[u].push_back(i);
  56.     }
  57. }
  58.  
  59. inline void Solve() {
  60.     FOR(i, 1, n) {
  61.         set<int, greater<int>> S; S.clear();
  62.         for (int j = i; j <= n; j++) {
  63.             S.erase(cnt[a[j]]);
  64.             ++cnt[a[j]];
  65.             S.insert(cnt[a[j]]);
  66.             int u = *S.begin();
  67.             Val[i][j] = max(0, 2 * u - (j - i + 1));
  68.         }
  69.         for (int j = i; j <= n; j++)
  70.             cnt[a[j]]--;
  71.     }
  72.     int Ans = 0;
  73.     FOR(i, 1, n) {
  74.         int cnt = Store[i].size();
  75.         if (cnt == 0) continue;
  76.         Store[i].push_back(n + 1);
  77.         FOR(j, 0, cnt)
  78.             dp[j][0] = dp[j][1] = -mod;
  79.         dp[0][0] = 1;
  80.         FOR(l, 0, cnt - 1)
  81.             FOR(j, 0, 1) {
  82.                 FOR(r, l + 1, cnt) {
  83.                     /// ko lay l + 1
  84.                     int dis = Store[i][r] - Store[i][l];
  85.                     if (r != cnt)
  86.                     dp[r][(j + dis) & 1] = max(dp[r][(j + dis) & 1], dp[l][j] - Val[Store[i][l] + 1][Store[i][r]]);
  87.                     if ((j + dis) & 1) {
  88.                         dp[r][0] = max(dp[r][0], dp[l][j] + 1 - Val[Store[i][l] + 1][Store[i][r] - 1]);
  89.                     }
  90.                 }
  91.             }
  92.         Ans = max(Ans, dp[cnt][0]);
  93.     }
  94.     cout << max(Ans - 2, 0) << '\n';
  95.     FOR(i, 1, n)
  96.         Store[i].clear();
  97. }
  98.  
  99. Ti20_ntson {
  100. //    freopen(TASK".INP","r",stdin);
  101. //    freopen(TASK".OUT","w",stdout);
  102.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  103.     int T = 1;
  104.     cin >> T;
  105.     while (T -- ) {
  106.         Read_Input();
  107.         Solve();
  108.     }
  109. }
  110.  
  111.  
  112.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/JzB1kS
language:
C++14 (gcc 8.3)
created:
7 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!