fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("O3")
  4. #pragma GCC optimize("O1")
  5. #pragma GCC optimize("O1")
  6. #pragma GCC optimize("unroll-loops")
  7. #pragma GCC optimize(3)
  8. #pragma GCC optimize("Ofast")
  9. #pragma GCC optimize("inline")
  10. #pragma GCC optimize("-fgcse")
  11. #pragma GCC optimize("-fgcse-lm")
  12. #pragma GCC optimize("-fipa-sra")
  13. #pragma GCC optimize("-ftree-pre")
  14. #pragma GCC optimize("-ftree-vrp")
  15. #pragma GCC optimize("-fpeephole2")
  16. #pragma GCC optimize("-ffast-math")
  17. #pragma GCC optimize("-fsched-spec")
  18. #pragma GCC optimize("-falign-jumps")
  19. #pragma GCC optimize("-falign-loops")
  20. #pragma GCC optimize("-falign-labels")
  21. #pragma GCC optimize("-fdevirtualize")
  22. #pragma GCC optimize("-fcaller-saves")
  23. #pragma GCC optimize("-fcrossjumping")
  24. #pragma GCC optimize("-fthread-jumps")
  25. #pragma GCC optimize("-freorder-blocks")
  26. #pragma GCC optimize("-fschedule-insns")
  27. #pragma GCC optimize("inline-functions")
  28. #pragma GCC optimize("-ftree-tail-merge")
  29. #pragma GCC optimize("-fschedule-insns2")
  30. #pragma GCC optimize("-fstrict-aliasing")
  31. #pragma GCC optimize("-falign-functions")
  32. #pragma GCC optimize("-fcse-follow-jumps")
  33. #pragma GCC optimize("-fsched-interblock")
  34. #pragma GCC optimize("-fpartial-inlining")
  35. #pragma GCC optimize("no-stack-protector")
  36. #pragma GCC optimize("-freorder-functions")
  37. #pragma GCC optimize("-findirect-inlining")
  38. #pragma GCC optimize("-fhoist-adjacent-loads")
  39. #pragma GCC optimize("-frerun-cse-after-loop")
  40. #pragma GCC optimize("inline-small-functions")
  41. #pragma GCC optimize("-finline-small-functions")
  42. #pragma GCC optimize("-ftree-switch-conversion")
  43. #pragma GCC optimize("-foptimize-sibling-calls")
  44. #pragma GCC optimize("-fexpensive-optimizations")
  45. #pragma GCC optimize("inline-functions-called-once")
  46. #pragma GCC optimize("-fdelete-null-pointer-checks")
  47. #define pb push_back
  48. #define BIT(mask, i) (mask & (1ll << (i)))
  49.  
  50. const int MAXN = 1e6 + 15;
  51.  
  52. int N;
  53. int A[MAXN], K[MAXN], dp[MAXN], high[MAXN], low[MAXN];
  54. bool vis1[MAXN], vis2[MAXN];
  55.  
  56.  
  57. namespace SubtaskFull {
  58.     int ma[1025][1025][22];
  59.     vector<int> g1[1025][22];
  60.  
  61.     void SOLVE() {
  62.         for (int i = 0; i <= 1023; i++) {
  63.             for (int j = 0; j <= 1023; j++) {
  64.                 if (!vis1[j]) continue;
  65.                 g1[i][__builtin_popcount(i ^ j)].pb(j);
  66.             }
  67.         }
  68.  
  69.  
  70.         int ans = 1;
  71.         for (int i = 1; i <= N; i++) {
  72.             dp[i] = 1;
  73.             if (K[i] <= 20) {
  74.                 for (int j = max(0, K[i] - 10); j <= min(K[i], 10); j++) {
  75.                     for (auto e1 : g1[high[i]][j]) {
  76.                         if (!vis1[e1]) continue;
  77.                         dp[i] = max(dp[i], ma[e1][low[i]][K[i] - j] + 1);
  78.                     }
  79.                 }
  80.             }
  81.             ans = max(ans, dp[i]);
  82.             for (int k = 0; k <= 1023; k++) {
  83.                 ma[high[i]][k][__builtin_popcount(k ^ low[i])] = max(ma[high[i]][k][__builtin_popcount(k ^ low[i])], dp[i]);
  84.             }
  85.         }
  86.         cout << ans;
  87.     }
  88. }
  89.  
  90.  
  91. void PROCESS() {
  92.     SubtaskFull :: SOLVE();
  93. }
  94.  
  95. signed main() {
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(0);
  98.     cout.tie(0);
  99.  
  100. //    freopen("hamming.inp", "r", stdin);
  101. //    freopen("hamming.out", "w", stdout);
  102.  
  103.     cin >> N;
  104.     for (int i = 1; i <= N; i++) {
  105.         cin >> A[i];
  106.         int x = 0;
  107.         for (int j = 19; j >= 10; j--) {
  108.             if (BIT(A[i], j)) x = x * 2 + 1;
  109.             else x = x * 2;
  110.         }
  111.         vis1[x] = true;
  112.         high[i] = x;
  113.         x = 0;
  114.         for (int j = 9; j >= 0; j--) {
  115.             if (BIT(A[i], j)) x = x * 2 + 1;
  116.             else x = x * 2;
  117.         }
  118.         vis2[x] = true;
  119.         low[i] = x;
  120.     }
  121.  
  122.     for (int i = 1; i <= N; i++) {
  123.         cin >> K[i];
  124.     }
  125.  
  126.     PROCESS();
  127. }
  128.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/JJEXEm
language:
C++14 (gcc 8.3)
created:
41 minutes 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!