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
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/VS8Wzc
language:
C++14 (gcc 8.3)
created:
5 years 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!