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 <cstdio>
#include <climits>
#include <algorithm>

typedef long long int64;

int64 dpm[61][201][201];
int64 dpf[61][201][201];
int64 sum[201][201];
int64 a[201];

int main() {
	int n;
	int64 m;
	scanf("%d%lld", &n, &m);

	for (int i = 0; i < n; i++)
		scanf("%lld", a + i);

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j <= n; j++)
			sum[j][i] = sum[j-1][i] + a[j-1];
	}

	int lm = 0;
	while (1ll << lm <= m)
		lm++;

	for (int l = 1; l < lm; l++) {
		int len_max = std::min((int64) n, 1ll << l);
		for (int len = 1; len <= len_max; len++) {
			for (int i = 0; i + len <= n; i++) {
				int j = i + len;

				dpf[l][i][j] = LLONG_MIN;
				int k_min = j - (int) std::min((int64) len, 1ll << (l - 1));
				int k_max = i + (int) std::min((int64) len, 1ll << (l - 1));

				for (int k = k_min; k <= k_max; k++) {
					int64 val = dpf[l-1][i][k] + dpf[l-1][k][j] + sum[j][k];
					if (dpf[l][i][j] < val)
						dpf[l][i][j] = val;
				}
			}
		}
	}

	int ll = 0;
	
	for (int l = 1; l <= lm; l++) {
		if ((m & (1ll << (l - 1))) == 0)
			continue;

		int64 w = 1 + (m & ((1ll << l) - 1));
		int64 cw = 1ll << (l - 1);

		int len_max = std::min((int64) n, w);
		for (int len = 1; len <= len_max; len++) {
			for (int i = 0; i + len <= n; i++) {
				int j = i + len;

				dpm[l][j][i] = LLONG_MIN;
				int k_min = j - (int) std::min((int64) len, w - cw);
				int k_max = i + (int) std::min((int64) len, cw);

				for (int k = k_min; k <= k_max; k++) {
					int64 val = dpf[l-1][i][k] + dpm[ll][j][k] + sum[j][k];
					if (dpm[l][j][i] < val)
						dpm[l][j][i] = val;
				}
			}
		}

		ll = l;
	}

	printf("%lld\n", dpm[lm][n][0]);
}