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

long long m, a[210], dp[210][210][68][2], pref[210];

bool used[210][210][68][2];

int n;

ll rec(int l, int r, int deep, int suff){
    if (l > r)
        return 0;
    if (used[l][r][deep+1][suff]){
        return dp[l][r][deep+1][suff];
    }
    if (deep == -1){
        return dp[l][r][deep+1][suff] = 0;
    }
    used[l][r][deep+1][suff] = 1;
    dp[l][r][deep+1][suff] = -1e18;
    for (int i = l-1; i <= r; i++){
        int l1 = l, r1 = i;
        int l2 = i+1, r2 = r;
        bool bb = 1;
        if (r1-l1+1 > (1ll<<(ll)(deep))){
            bb = 0;
        }
        if (suff == 0){
            if (r2-l2+1 > (1ll<<(ll)(deep)))
                bb = 0;
        }
        else {
            if (((m & (1ll<<(ll)(deep))) == 0 && l2 <= r2 )|| r2-l2+1 > m-(1ll<<(ll)(deep))+1)
                bb = 0;
        }
        if (bb == 0){
            continue;
        }
        dp[l][r][deep+1][suff] = max(dp[l][r][deep+1][suff], rec(l1, r1, deep-1, 0)+rec(l2, r2, deep-1, suff)+pref[r2]-pref[l2-1]);
        //cout << l << ' ' << r << ' ' << i << ' ' << deep << ' ' << suff << ' ' << rec(l1, r1, deep-1, 0) << ' ' << rec(l2, r2, deep-1, suff) << ' ' << pref[r2]-pref[l2-1] << endl;
    }
    return dp[l][r][deep+1][suff];
}

int main(int argc, char *argv[]){

    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    ll mxbt = 0;
    for (ll bt = 0; bt < 63; bt++){
        if ((1ll<<bt) & m)
            mxbt = bt;
    }
    cout << rec(1, n, mxbt, 1);


}