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

using namespace std;

const int MAX_VALUES = 300;
long long values[MAX_VALUES];
long long partial_sums[MAX_VALUES];

bool precomputed[MAX_VALUES][MAX_VALUES][70];
int precomputed_vals[MAX_VALUES][MAX_VALUES][70];


unsigned long long lower_two_power(unsigned long long v) {
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;
    v++;
    return v / 2;
}

long long bit_count(long long k2) {
    long long bits = 0;
    for(bits = 0; k2 != 0; ++bits) k2 >>= 1;
    return bits;
}

long long compute_result(int left, int right, long long k) {
    long long nearest_two_power = lower_two_power(k);
    bool k_is_power = (1 << bit_count(k)) == (k + 1);
    int bits = bit_count(k + 1);
    if (k_is_power && precomputed[left][right][bits]) {
        return precomputed_vals[left][right][bits];
    }
    long long full_result = -1000000000000000000;
    if (right - left > (k + 1)) {
        return full_result;
    }
    if (k == 0) {
        return 0;
    }
    if (right == left + 1) {
        if (values[left] > 0) {
            return values[left] * (bits - 1);
        }
        else {
            return 0;
        }
    }
    for(int i=left+1; i<right; i++) {
        long long result1 = compute_result(left, i, nearest_two_power - 1);
        long long result2 = compute_result(i, right, k - nearest_two_power);
        full_result = max(result1 + result2 + partial_sums[right] - partial_sums[i], full_result);
    }
    if (k_is_power) {
        precomputed[left][right][bits] = true;
        precomputed_vals[left][right][bits] = full_result;
    }
    return full_result;
}


int main() {
    long long n, k;
    cin >> n >> k;
    partial_sums[0] = 0;
    for (int i=0; i<n; i++) {
        cin >> values[i];
        partial_sums[i+1] = partial_sums[i] + values[i];
    }
    cout << compute_result(0, n, k) << endl;
};