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
#include <iostream>
#include <algorithm>

const int N = 201;
const int B = 64;

int64_t M[B+1][N][N];
int64_t Z[B+1][N][N];
int64_t A[N], S[N][N];
int64_t INF = 100000000000000000ll;

int main() {
    std::ios_base::sync_with_stdio(0);
    int64_t n,m;
    std::cin >> n >> m;
    for (int i=0;i<n;++i) std::cin >> A[i];
    for (int i=0;i<n;++i) {
        S[i][i+1]  = A[i];
        for (int j=i+1;j<n;++j) {
            S[i][j+1] = S[i][j] + A[j];
        }
    }
    
    for (int b=0;b<=B;++b) {
        for (int i=0;i<n;++i) {
            for (int j=i+1;j<=n;++j) {
                M[b][i][j] = Z[b][i][j] = -INF;
            }
        }
    }
    for (int i=0;i<n;++i) {
        M[0][i][i+1] = 0;
    }
    Z[0][n-1][n] = 0;

    for (int b=1;b<=B;++b) {
        for (int i=0;i<n;++i) {
            for (int j=i+1;j<=n;++j) {
                for (int k=i;k<=j;++k) {
                    M[b][i][j] = std::max(M[b][i][j], S[k][j] + M[b-1][i][k] + M[b-1][k][j]);
                }
            }
        }
    }
    for (int b=1;b<=B;++b) {
        for (int i=0;i<n;++i) {
            if ((1ll<<(b-1)) & m) {
                for (int k=i;k<=n;++k) {
                    Z[b][i][n] = std::max(Z[b][i][n], S[k][n] + M[b-1][i][k] + Z[b-1][k][n]);
                }
            } else {
                Z[b][i][n] = std::max(Z[b][i][n], S[n][n] + Z[b-1][i][n] + Z[b-1][n][n]);
            }
        }
    }
    int rb = 0;
    while ((1ll << rb) < m) ++rb;

    std::cout << Z[rb+1][0][n] << std::endl;
    return 0;
}