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
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)
#define LLG(x) LL x; scanf("%lld", &x)

typedef long long LL;

const LL INF = 8000000000000000000LL;
LL a[200], s[201];
LL res[201][201][61], resm[201][201][61];

int main() {
	INT(n);
	LLG(m);
	REP(i,n) scanf("%lld", &a[i]);
	s[0] = 0;
	REP(i,n) s[i + 1] = s[i] + a[i];
	REP(i,n+1) FOR(j,i,n+1) REP(k,61) res[i][j][k] = resm[i][j][k] = -INF;
	REP(i,n+1) REP(k,61) res[i][i][k] = resm[i][i][k] = 0;
	REP(i,n) res[i][i + 1][0] = resm[i][i + 1][0] = 0;
	FOR(d,1,n+1) REP(i,n-d+1) {
		int j = i + d;
		FOR(k,1,61) {
			LL r = -INF;
			FOR(x,i,j+1)
				if (res[i][x][k - 1] > -INF && res[x][j][k - 1] > -INF)
					r = max(r, res[i][x][k - 1] + res[x][j][k - 1] + s[j] - s[x]);
			res[i][j][k] = r;
			if (!(m & (1LL << (k - 1)))) {
				resm[i][j][k] = resm[i][j][k - 1];
				continue;
			}
			r = -INF;
			FOR(x,i,j+1)
				if (res[i][x][k - 1] > -INF && resm[x][j][k - 1] > -INF)
					r = max(r, res[i][x][k - 1] + resm[x][j][k - 1] + s[j] - s[x]);
			resm[i][j][k] = r;
		}
	}
	printf("%lld\n", resm[0][n][60]);
}