fork(11) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<long long> a;
  4. map<pair<long long, int>, long long> dp;
  5. int k;
  6. long long f(long long mask, int n) { // 2^K  * N
  7.     if (dp.count({mask, n})) return dp[ {mask, n}];
  8.     else if (n == 0) return 0;
  9.     long long &ans = dp[ {mask, n}];
  10.     long long msk = mask, bit, pw = 1, ck = 1;
  11.     while (msk) { // O(K)
  12.         bit = msk % 10;
  13.         msk /= 10;
  14.         if (bit > 0) // put nth element on ck position
  15.             ans = max(ans, (a[n - 1] & ck) + f(mask - pw, n - 1));
  16.         ck++;
  17.         pw *= 10;
  18.     }
  19.     return ans;
  20. }
  21. int main() {
  22.     int t;
  23.     cin >> t;
  24.     while (t--) {
  25.         int n;
  26.         cin >> n >> k;
  27.         a.resize(n);
  28.         for (int i = 0; i < n; i++)
  29.             cin >> a[i];
  30.         long long mask = 2;
  31.         for (int i = 2; i <= k; i++)  {
  32.             mask = mask * 10 + 2;
  33.         }
  34.         cout << f(mask, n) << '\n';
  35.         dp.clear();
  36.     }
  37.     return 0;
  38. }
Success #stdin #stdout 0s 5600KB
comments (?)
stdin
copy 
2
6
3
1 2 3 4 5 6
5
5
1 2 3 4 5
stdout
copy 
9
15
https://ideone.com/hJ2KS3
language:
C++14 (gcc 8.3)
created:
2 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!