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
#include<bits/stdc++.h>
using namespace std;
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.first << ", " << p.second << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
template<class T> int size(T && a) { return a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

template<class T> auto create(T x) { return x; }
template<class... Ts> auto create(int n, Ts... x) {
	return vector(n, create(x...));
}

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

	int n;
	LL m;
	cin >> n >> m;
	vector<LL> a(n), pref(n + 1);
	REP(i, n) cin >> a[i];
	FOR(i, 1, n) pref[i] = pref[i - 1] + a[i - 1];

	LL inf = 1e18, undef = -inf - 7;
	auto dp = create(2, n + 1, n + 1, 60, undef);
	auto solve = [&](auto self, int l, int r, int b, int s) -> LL {
		if(l > r) return 0;
		if(b == -1) return (l == r ? 0 : -inf);
		LL &val = dp[s][l][r][b];
		if(val != undef) return val;
		val = -inf;
		if(s && (m & (1LL << b)) == 0) val = self(self, l, r, b - 1, true);
		else FOR(x, l - 1, r) {
			val = max(val, 
				self(self, l, x, b - 1, false) + 
				self(self, x + 1, r, b - 1, s) + 
				pref[r] - pref[x]
			);
		}
		return val;
	};

	cout << solve(solve, 1, n, 59, true);
}