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

using namespace std;

typedef long long int ll;

#define INF 2200000000000000000LL

ll n, m, a[210], dp[66][210][210][2], bt, sum[210];

int main () {
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    for (int b=0; b<=62; b++) {
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=n; j++) {
                dp[b][i][j][0] = dp[b][i][j][1] = -INF;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        dp[0][i][i][0] = 0;
        if (m & 1) {
            dp[0][i][i][0] = max(a[i], 0LL);
        }
        
        dp[0][i][i][1] = max(a[i], 0LL);
        
        if (i < n) {
            if (m & 1) {
                dp[0][i][i+1][0] = a[i+1];
            } else {
                dp[0][i][i+1][0] = -INF;
            }
            dp[0][i][i+1][1] = a[i+1];
        }
    }
    ll start;
    
    for (ll b = 62; b>=0; b--) {
        if ((1<<b) & m) {
            start = b;
            break;
        }
    }
  //  cout << start << endl;
    
    for (int b=0; b<start; b++) {
        for (int i=1; i<=n; i++) {
            //for (int j=i; j<=min(n, i+(2LL << (ll)(b+1))-1); j++) {
            dp[b][i][i-1][0] = 0;
            dp[b][i][i-1][1] = 0;
            for (int j=i; j<=n; j++) {
                dp[b+1][i][j][0] = dp[b][i][j][0];
                dp[b+1][i][j][1] = dp[b][i][j][1];
                bt = (((1LL << (ll)(b+1)) & m) > 0);
                for (int k=i; k<=j; k++) {
                    if ((dp[b][i][k-1][1] != -INF) && (dp[b][k][j][1] != -INF)) {
                        dp[b+1][i][j][1] = max(dp[b+1][i][j][1], dp[b][i][k-1][1] + dp[b][k][j][1] + sum[j] - sum[k-1]);
                    }
                    if (bt) {
                        if (dp[b][i][k-1][1] != -INF && dp[b][k][j][0] != -INF) {
                            dp[b+1][i][j][0] = max(dp[b+1][i][j][0], dp[b][i][k-1][1] + dp[b][k][j][0] + sum[j] - sum[k-1]);
                        }
                        dp[b+1][i][j][0] = max(dp[b+1][i][j][0], dp[b][i][j][1]);
                    }
                }
            }
        }
    }
    cout << dp[start][1][n][0] << endl;
}