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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 200;
const ll INF = 1e18 + 2137;

int n, lg;
ll m, a;
ll pref[N + 5], dp[N + 5][N + 5][2], ans[N + 5][N + 5][2];

void Prepare(){
	cin >> n >> m;
	while((1ll << lg) <= m){
		lg ++;
	}
	for(int i=1; i<=n; i++){
		cin >> a;
		pref[i] = pref[i - 1] + a;
		for(int j=i+1; j<=n; j++){
			dp[i][j][0] = (-2ll) * INF;
			dp[i][j][1] = (-2ll) * INF;
		}
	}
}

bool Check(const int &x, const int &y, const int &z, const int &id){
	return ((dp[x][z - 1][1] + dp[z][y][id] + pref[y] - pref[z - 1]) <= ((-1ll) * INF));
}

void Propagate(const int &x, const int &y, const int &id){
	for(int h=x; h<=y; h++){
		if(!Check(x, y, h, id)){
			ans[x][y][id] = max(ans[x][y][id], dp[x][h - 1][1] + dp[h][y][id] + pref[y] - pref[h - 1]);
		}
	}	
}

ll Solve(){
	for(int k=0; k<lg; k++){
		for(int i=1; i<=n; i++){
			for(int j=i; j<=n; j++){
				ans[i][j][0] = dp[i][j][0];
				ans[i][j][1] = dp[i][j][1];
				Propagate(i, j, 1);
				if(!((m >> k) & 1ll)){
					continue;
				}
				ans[i][j][0] = dp[i][j][1];
				Propagate(i, j, 0);
			}
		}
		for(int i=1; i<=n; i++){
			for(int j=i; j<=n; j++){
				dp[i][j][0] = ans[i][j][0];
				dp[i][j][1] = ans[i][j][1];
			}
		}
	}
	return ans[1][n][0];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	Prepare();
	cout << Solve() << "\n";
	
	return 0;
}