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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

long long n;
long long m;
long long pm;

long long t[205][205][64][4];
long long a[205];
long long s[205][205];
long long p[64];
long long q[64];

long long small = -1000000000000000000LL;

int main(){
    scanf("%lld%lld", &n, &m);
    p[0] = 1;
    if ((n == 1) && (m == 0)){
        printf("0\n");
        return 0;
    }
    for (long long i = 1; i < 64; i++){
        p[i] = p[i - 1] * 2;
    }
    while (p[pm] <= m){
        pm++;
    }
    q[pm - 1] = m;
    for (long long i = pm - 2; i >= 0; i--){
        if (m & (1LL << i)){
            q[i] = q[i + 1] - p[i + 1];
        }
        else {
            q[i] = q[i + 1];
        }
    }
    for (long long i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    for (long long i = 1; i <= n; i++){
        long long r = 0;
        for (long long j = i; j <= n; j++){
            r += a[j];
            s[i][j] = r;
        }
    }
    for (long long k = 0; k <= pm; k++){
        for (long long i = 1; i <= n; i++){
            for (long long j = i; j <= n; j++){
                t[i][j][k][0] = small;
                t[i][j][k][1] = small;
                t[i][j][k][2] = small;
                t[i][j][k][3] = small;
            }
        }
    }
    for (long long i = 1; i <= n; i++){
        t[i][i][0][0] = 0;
        t[i][i][0][1] = a[i];
        t[i][i][0][2] = 0;
        if (q[0] > 0){
            t[i][i][0][3] = a[i];
        }
    }
    for (long long k = 1; k <= pm; k++){
        for (long long i = 1; i <= n; i++){
            for (long long j = i; j <= std::min(n, i + p[k] - 1); j++){
                if ((m & (1LL << k)) && (!(m & (1LL << (k - 1)))) && (j <= i + p[k - 1] - 1)){
                    t[i][j][k][3] = s[i][j] + t[i][j][k - 1][2];
                }
                if ((!(m & (1LL << k))) && (!(m &(1LL << (k - 1)))) && (j <= i + p[k - 1] - 1)){
                    t[i][j][k][2] = t[i][j][k - 1][2];
                }
                for (long long l = std::max(i-1, j - p[k - 1]); l <= std::min(j, i + p[k - 1] - 1); l++){
                    t[i][j][k][0] = std::max(t[i][j][k][0], t[i][l][k - 1][0] + t[l + 1][j][k - 1][1]);
                    t[i][j][k][1] = std::max(t[i][j][k][1], s[i][j] +t[i][l][k - 1][0] + t[l + 1][j][k - 1][1]);
                    if (m & (1LL << k)){
                        t[i][j][k][2] = std::max(t[i][j][k][2], t[i][l][k - 1][0] + t[l + 1][j][k - 1][1]);
                    }
                    if ((m & (1LL << k)) && (m & (1LL << (k - 1))) && (j - l <= q[k - 1])){
                            t[i][j][k][3] = std::max(t[i][j][k][3], s[i][j] + t[i][l][k - 1][0] + t[l + 1][j][k - 1][3]);
                    }
                    if ((!(m & (1LL << k))) && (m & (1LL << (k - 1))) && (j - l <= q[k - 1])){
                        t[i][j][k][2] = std::max(t[i][j][k][2], t[i][l][k - 1][0] + t[l + 1][j][k - 1][3]);
                    }
                }
                /*for (long long s = 0; s < 4; s++){
                    printf("(%lld %lld %lld %lld = %lld)\n", i, j, k, s, t[i][j][k][s]);
                }*/
            }
        }
    }
    printf("%lld\n", t[1][n][pm][2]);
}