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
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
const int MAXN = 205;
const int MAXBITS = 63;

struct dpresult
{
  bool viable;
  i64 value;
};

inline dpresult combine(const dpresult &a, const dpresult &b)
{
  if (!a.viable || !b.viable)
  {
    return {false, 0};
  }
  return {true, a.value + b.value};
}

inline bool operator<(const dpresult &a, const dpresult &b)
{
  if (a.viable == b.viable)
  {
    return a.value < b.value;
  }
  return a.viable < b.viable;
}

int n;
i64 m;
dpresult dp[MAXN][MAXN][MAXBITS][2];
i64 input[MAXN];

void read()
{
  scanf("%d%lld", &n, &m);
  for (int i = 0; i < n; i++)
  {
    scanf("%lld", &input[i]);
  }
}

void computeDP(int start, int end, i64 bits, int cutoff)
{
  // Not viable
  if ((i64)(end - start + 1) > (1LL << bits))
  {
    dp[start][end][bits][cutoff] = {false, 0};
    return;
  }

  // Bottom
  if (bits == 0)
  {
    dp[start][end][bits][cutoff] = {true, 0};
    return;
  }

  // Forced to ignore bit
  if (cutoff == 1 && (m & (1LL << (bits - 1LL))) == 0)
  {
    dp[start][end][bits][cutoff] = dp[start][end][bits - 1][cutoff];
    return;
  }

  dpresult result = {false, 0};

  // All 0
  result = max(result, dp[start][end][bits - 1][0]);

  // Split
  i64 currentSum = 0;
  for (int sufstart = end; sufstart > start; sufstart--)
  {
    currentSum += input[sufstart];
    dpresult combined = combine(dp[start][sufstart - 1][bits - 1][0], dp[sufstart][end][bits - 1][cutoff]);
    result = max(result, combine(combined, {true, currentSum}));
  }

  // All 1
  currentSum += input[start];
  result = max(result, combine(dp[start][end][bits - 1][cutoff], {true, currentSum}));

  dp[start][end][bits][cutoff] = result;
}

i64 solve()
{
  for (int d = 0; d < n; d++)
  {
    for (int start = 0; start + d < n; start++)
    {
      for (i64 bits = 0; bits < MAXBITS; bits++)
      {
        for (int cutoff = 0; cutoff <= 1; cutoff++)
        {
          computeDP(start, start + d, bits, cutoff);
        }
      }
    }
  }
  return dp[0][n - 1][MAXBITS - 1][1].value;
}

int main()
{
  read();
  printf("%lld\n", solve());
  return 0;
}