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
// Author: Kamil Nizinski
// NOLINT(legal/copyright)
#ifdef LOCAL
#ifdef COLOR
#include "bits/cp_local_color.h"
#else
#include "bits/cp_local.h"
#endif
#else
#include "bits/stdc++.h"
#define debug_arr(arr_name, first, last)
#define debug(...)
#define cerr if (false) cerr
#define speed_of_cin_and_cout ios_base::sync_with_stdio(0), cin.tie(0)
#define local if (false)
#endif
#define ft first
#define sd second
#define psb push_back
#define sz(a) (static_cast<int>((a).size()))
using namespace std;  // NOLINT(build/namespaces)
typedef int64_t LL;
typedef uint64_t LLU;
typedef long double LD;
typedef pair<int, int> PII;

const int kMaxN = 200, kMaxLogM = 59;
const LL kMinInf = LL{-5000000000000000007};
// Maximum log_2 from the most significant bit of m (is 59).
// log_2 is index of its position starting indexing from 0.
// + 2 to get the number of numbers of bits considered (starting from 0).
LL dp_full[kMaxLogM + 2][kMaxN + 1][kMaxN + 1];
LL dp_restricted[kMaxLogM + 2][kMaxN + 1][kMaxN + 1];
LL sums_on_ranges[kMaxN + 1][kMaxN + 1];
LL prefix_sums[kMaxN + 1];

LL solve() {
  int n;
  LL m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    LL a;
    cin >> a;
    prefix_sums[i + 1] = prefix_sums[i] + a;
  }
  for (int i = 0; i <= n; i++)
    for (int j = i; j <= n; j++)
      sums_on_ranges[i][j] = prefix_sums[j] - prefix_sums[i];
  for (int i = 0; i <= n; i++) {
    dp_full[0][i][i] = dp_restricted[0][i][i] = LL{0};
    if (i + 1 <= n)
      dp_full[0][i][i + 1] = dp_restricted[0][i][i + 1] = LL{0};
    for (int j = i + 2; j <= n; j++)
      dp_full[0][i][j] = dp_restricted[0][i][j] = kMinInf;
  }
  int bits;
  for (bits = 0; (m >> (bits)) > LL{0}; bits++) {
    // I can use more bits so I explore this option.
    for (int i = 0; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        dp_full[bits + 1][i][j] = kMinInf;
        for (int k = i; k <= j; k++) {
          LL left = dp_full[bits][i][k];
          if (left == kMinInf) continue;
          LL right = dp_full[bits][k][j];
          if (right == kMinInf) continue;
          dp_full[bits + 1][i][j]
          = max(dp_full[bits + 1][i][j], left + right + sums_on_ranges[k][j]);
        }
        dp_restricted[bits + 1][i][j] = kMinInf;
        if (m & (LL{1} << bits)) {
          for (int k = i; k <= j; k++) {
            LL left = dp_full[bits][i][k];
            if (left == kMinInf) continue;
            LL right = dp_restricted[bits][k][j];
            if (right == kMinInf) continue;
            dp_restricted[bits + 1][i][j]
            = max(dp_restricted[bits + 1][i][j],
              left + right + sums_on_ranges[k][j]);
          }
        } else {
          LL left = dp_restricted[bits][i][j];
          if (left != kMinInf) {
            dp_restricted[bits + 1][i][j]
            = max(dp_restricted[bits + 1][i][j], left);
          }
        }
      }
    }
  }
  return dp_restricted[bits][0][n];
}

int main() {
  speed_of_cin_and_cout;
  int test_cases_num = 1;
//   cin >> test_cases_num;
  for (int i = 1; i <= test_cases_num; i++) {
    local if (test_cases_num > 1) cerr << "Test #" << i << ":\n";
    cout << solve() << "\n";
    local if (test_cases_num > 1) cerr << "End of test #" << i << ".\n";
  }
  return 0;
}