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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 210;
const int MAXB = 64;

using ll = long long int;
const ll INF = 1000000000000000000LL;

ll a[MAXN];
ll DP[MAXB][MAXN][MAXN][2];
//DP[l][r][b][md] - najlepszy koszt ciągu (a_l, ..., a_r) gdzie b_i nale¿y do przedziału:
//md = 0 -> (0, 2 ** b - 1)
//md = 1 -> (0, (2 ** b - 1) & m)

ll sum[MAXN][MAXN];
//sum[l][r] = a_l + a_{l+1} + ... + a_{r-1} + a_r

int llog(ll m) {
    int ret = 0;
    ll p = 1;
    while (m >= p) {
        p *= 2;
        ret++;
    }
    return ret;
}

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

    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    for (int l = 1; l <= n; l++) {
        sum[l][l] = a[l];
        for (int r = l + 1; r <= n; r++) {
            sum[l][r] = sum[l][r - 1] + a[r];
        }
    }

    for (int l = 1; l <= n; l++) {
        for (int r = l + 1; r <= n; r++) {
            DP[0][l][r][0] = -INF;
            DP[0][l][r][1] = -INF;
        }
    }

    for (int b = 1; b <= llog(m); b++) {
        bool mm = (m & (1LL << (b - 1)));
        if (mm) {
            for (int l = 1; l <= n; l++) {
                for (int r = l; r <= n; r++) {
                    DP[b][l][r][0] = DP[b - 1][l][r][0] + max(0LL, sum[l][r]);
                    DP[b][l][r][1] = max(DP[b - 1][l][r][0], DP[b - 1][l][r][1] + sum[l][r]);
                    for (int t = l; t < r; t++) {
                        DP[b][l][r][0] = max(DP[b][l][r][0], DP[b - 1][l][t][0] + DP[b - 1][t + 1][r][0] + sum[t + 1][r]);
                        DP[b][l][r][1] = max(DP[b][l][r][1], DP[b - 1][l][t][0] + DP[b - 1][t + 1][r][1] + sum[t + 1][r]);
                    }
                }
            }
        }
        else {
            for (int l = 1; l <= n; l++) {
                for (int r = l; r <= n; r++) {
                    DP[b][l][r][0] = DP[b - 1][l][r][0] + max(0LL, sum[l][r]);
                    DP[b][l][r][1] = DP[b - 1][l][r][1];
                    for (int t = l; t < r; t++) {
                        DP[b][l][r][0] = max(DP[b][l][r][0], DP[b - 1][l][t][0] + DP[b - 1][t + 1][r][0] + sum[t + 1][r]);
                    }
                }
            }
        }
    }

    printf("%lld\n", DP[llog(m)][1][n][1]);
}