fork download
  1. //Optimise
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define multitest 1
  6. #ifdef Debug
  7. #define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
  8. template <typename Arg1>
  9. void ZZ(const char *name, Arg1 &&arg1)
  10. {
  11. std::cerr << name << " = " << arg1 << endl;
  12. }
  13. template <typename Arg1, typename... Args>
  14. void ZZ(const char *names, Arg1 &&arg1, Args &&... args)
  15. {
  16. const char *comma = strchr(names + 1, ',');
  17. std::cerr.write(names, comma - names) << " = " << arg1;
  18. ZZ(comma, args...);
  19. }
  20. #else
  21. #define db(...)
  22. #endif
  23.  
  24. using ll = long long;
  25. #define f first
  26. #define s second
  27. #define pb push_back
  28. const long long mod = 1000000007;
  29. auto TimeStart = chrono::steady_clock::now();
  30.  
  31. const int nax = 25;
  32. int n, k;
  33. vector<int> a(nax);
  34. int dp[21][21][40000]; // 40000 is chosen for safety it is the max value xor of k elements can assume that I assumed
  35.  
  36. int solve(int pos, int prevXor, int rem)
  37. {
  38. if (pos == n) // Exhausted the element choice
  39. {
  40. if (rem == 0) // You have chosen k elements somehow, so this is valid
  41. return prevXor;
  42. else
  43. return 0; // Something went wrong returning the least value possible
  44. }
  45. if (rem == 0) // Whoa! You have to finish the taking process
  46. return prevXor;
  47. int &ret = dp[pos][rem][prevXor];
  48. if (ret >= 0) // Already solved
  49. return ret;
  50. ret = 0;
  51. // Now me have a choice
  52. ret = max(solve(pos + 1, prevXor, rem), solve(pos + 1, prevXor ^ a[pos], rem - 1));
  53. // Take the element or not -- Choose the best
  54. return ret;
  55. }
  56.  
  57. void solve()
  58. {
  59. cin >> n >> k;
  60. memset(dp, -1, sizeof(dp));
  61. for (int i = 0; i < n; ++i)
  62. cin >> a[i];
  63. cout << solve(0, 0, k) << '\n';
  64. }
  65.  
  66. int main()
  67. {
  68. ios_base::sync_with_stdio(0);
  69. cin.tie(0);
  70. int t = 1;
  71. #ifdef multitest
  72. cin >> t;
  73. #endif
  74. while (t--)
  75. solve();
  76. #ifdef TIME
  77. cerr << "\n\nTime elapsed: " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n";
  78. #endif
  79. return 0;
  80. }
Success #stdin #stdout 0s 84160KB
stdin
Standard input is empty
stdout
Standard output is empty