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
 98
 99
100
101
102
103
104
105
#include <bits/stdc++.h>

using namespace std;

#define int long long

const bool debug = false;

#define cerr if (!debug) {} else cout 
#define pisz(x) cerr << #x << ": " << x << endl;

const int MAX_N = 210;
const int MAX_BIT = 60;
const int INF = numeric_limits<int>::max() - 10;

int dp[MAX_BIT + 2][MAX_N + 2][MAX_N + 2];
int spec[MAX_BIT + 2][MAX_N + 2][MAX_N + 2];
int n, m;

int pref[MAX_N + 2];

void init() {
    for (int dl = 0; dl <= MAX_BIT; dl++) {
        for (int i = 0; i <= MAX_N; i++) {
            for (int j = 0; j <= MAX_N; j++) {
                spec[dl][i][j] = dp[dl][i][j] = -INF;
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    init();
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> pref[i];
        dp[0][i][i] = max(0LL, pref[i]);
        if (i > 1) {
            dp[0][i - 1][i] = pref[i];
        }
        
        if (1 & m) {
            spec[0][i][i] = dp[0][i][i];
            spec[0][i - 1][i] = dp[0][i - 1][i];
        } else {
            spec[0][i][i] = 0;
        }
        
        pref[i] += pref[i - 1];
    }
    
    if (m == 0) {
        cout << 0;
        return 0;
    }
    
    for (int dl = 1; dl <= MAX_BIT; dl++) {
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                // Liczymy spec:
                if (m & (1LL << dl)) {
                    // Wszystkie z zerem na początku.
                    spec[dl][i][j] = dp[dl - 1][i][j];
                    if (spec[dl - 1][i][j] != -INF) {
                        // Wszystkie z jedynką na początku.
                        spec[dl][i][j] = max(spec[dl][i][j], spec[dl - 1][i][j] + pref[j] - pref[i - 1]);
                    }
                    
                    for (int k = i; k < j; k++) {
                        if (dp[dl - 1][i][k] != -INF && spec[dl - 1][k + 1][j] != -INF) {
                            // Na [i, k] zero najbardziej znaczące, na [k + 1, j] jedynka.
                            spec[dl][i][j] = max(spec[dl][i][j], dp[dl - 1][i][k] + spec[dl - 1][k + 1][j] + pref[j] - pref[k]);
                        }
                    }   
                } else {
                    spec[dl][i][j] = spec[dl - 1][i][j];
                }
                
                // Liczym dp:
                if (dp[dl - 1][i][j] != -INF) {
                    // Wszystkie z takim samym najbardziej znaczącym bitem.
                    dp[dl][i][j] = dp[dl - 1][i][j] + max(0LL, pref[j] - pref[i - 1]);
                    //cerr << dl << " " << i << " " << j << "   "; pisz(dp[dl][i][j]);
                }
                for (int k = i; k < j; k++) {
                    if (dp[dl - 1][i][k] != -INF && dp[dl - 1][k + 1][j] != -INF) {
                        // Na [i, k] zero najbardziej znaczące, na [k + 1, j] jedynka.
                        dp[dl][i][j] = max(dp[dl][i][j], dp[dl - 1][i][k] + dp[dl - 1][k + 1][j] + pref[j] - pref[k]);
                    }
                }
            }
        }
    }
    
    cout << spec[MAX_BIT][1][n];
    
    return 0;
}
/*

 */