1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const ll INF = 1000'000'000'000'000'000LL;

bool filled[2][64][207][207];
ll dp[2][64][207][207];

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  ll m;
  cin >> n >> m;
  vector <ll> a(n+1);
  for(int i=1; i<=n; i++) {
    cin >> a[i];
    a[i] += a[i-1];
  }
  auto sum = [&](int p, int q) {
    return a[q] - a[p];
  };
  function<ll(bool, int, int, int)> foo = [&](bool available, int lvl, int p, int q) {
    if (p >= q) return 0LL;
    if (lvl == -1) {
      if (q - p > 1) return -INF;
      else return sum(p, p);
    }
    if(filled[available][lvl][p][q]) {
       return dp[available][lvl][p][q];
    }
    ll res = -INF;
    if(available or ((1LL<<lvl) & m)) {
      for(int k=p; k<=q; k++) {
        ll cur_res = foo(true, lvl-1, p, k) + foo(available, lvl-1, k, q) + sum(k, q);
        res = max(res, cur_res);
      }
    } else {
      res = foo(available, lvl-1, p, q);
    }
    filled[available][lvl][p][q] = true;
    return dp[available][lvl][p][q] = res;
  };
  cout << foo(false, 63, 0, n) << "\n";
}