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
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
constexpr LL inf = 0x3f3f3f3f3f3f3f3f;
LL dp2[200][200][61], dp[200][200][61];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	LL m;
	cin >> n >> m;

	vector<LL> a(n);
	for(LL &ai : a)
		cin >> ai;

	int mx_bits = 0;
	while((1LL << mx_bits) < m + 1)
		++mx_bits;
	++mx_bits;

	vector<LL> pref(n);
	REP(i, n) {
		if(i != 0)
			pref[i] = pref[i - 1];
		pref[i] += a[i];
	}

	auto sum = [&](int l, int r) {
		if(l == 0)
			return pref[r];
		return pref[r] - pref[l - 1];
	};

	REP(i, n)
		REP(j, n)
			REP(b, mx_bits)
				dp[i][j][b] = dp2[i][j][b] = -inf;
	//vector<vector<vector<LL>>> dp2(n, vector<vector<LL>>(n, vector<LL>(mx_bits, -inf))), dp = dp2;
	FOR(len, 1, n)
		REP(l, n - len + 1) {
			int r = l + len - 1;
			REP(b, mx_bits) {
				if(b == 0) {
					if(l == r)
						dp[l][r][b] = dp2[l][r][b] = 0;
					continue;
				}
				if(~m & (1LL << (b - 1))) {
					dp[l][r][b] = dp[l][r][b - 1];
					FOR(first, l, r + 1) {
						LL curr = 0;
						if(first != l)
							curr += dp2[l][first - 1][b - 1];
						if(first != r + 1)
							curr += dp2[first][r][b - 1] + sum(first, r);
						dp2[l][r][b] = max(dp2[l][r][b], curr);
					}
				}
				else {
					FOR(first, l, r + 1) {
						LL curr2 = 0;
						if(first != l)
							curr2 += dp2[l][first - 1][b - 1];
						LL curr1 = curr2;
						if(first != r + 1) {
							curr2 += sum(first, r);
							curr1 = curr2;
							curr2 += dp2[first][r][b - 1];
							curr1 += dp[first][r][b - 1];
						}
						dp2[l][r][b] = max(dp2[l][r][b], curr2);
						dp[l][r][b] = max(dp[l][r][b], curr1);
					}
				}
			}
		}

	cout << dp[0][n - 1][mx_bits - 1];
}