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
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <climits>
#define LL long long
#define MIN_VALUE LLONG_MIN
#define MAX_LENGTH 2010
#define TMP_LENGTH 70

using namespace std;

LL m_values[MAX_LENGTH], max_values[MAX_LENGTH];

int max_bits(LL m) {
    int v = 0;
    LL tmp = 1;
    while (tmp <= m) {
        tmp *= 2;
        v++;
    }
    return v;
}

int count_bits(LL m) {
    int c = 0;
    while (m) {
        m &= m - 1;
        c++;
    }
    return c;
}


LL max_value_with_bits(LL max_value, int bits) {
    LL value = 0, new_value;
    bool tmp[TMP_LENGTH];
    int used_bit;
    if (bits == 0)
        return 0;
    for (int i = 0; i < bits; i++) {
        tmp[i] = true;
        value = 2*value + 1;
    }
    if (value > max_value)
        return -1;

    for (int i = bits; i < TMP_LENGTH; i++) {
        tmp[i] = false;
    }

    used_bit = bits - 1;
    while (used_bit >= 0) {
        if (tmp[used_bit] && !tmp[used_bit+1]) {
            new_value = value + (1L<<(used_bit+1)) - (1L<<(used_bit));
            if (new_value > max_value) {
                used_bit--;
                continue;
            }
            value = new_value;
            tmp[used_bit+1] = true;
            tmp[used_bit] = false;
            used_bit++;
        } else {
            used_bit--;
        }
    }
    return value;
}

LL optimise(LL *music, int N, LL m, int t){
    int b, start_bit, end_bit, inc, max_bit = max_bits(m), n = N - t - 1;
    LL value, tmp_m, tmp_value, max_value = max_values[n];
    if (music[n] < 0) {
        for (b=0; b <= max_bit; b++){
            tmp_m = max_value_with_bits(m, b);
            if (tmp_m <= m_values[n]) continue;
            m_values[n] = tmp_m;
            if (n > 0) {
                tmp_value = optimise(music, N, tmp_m-1, t+1);
            } else {
                tmp_value = 0;
            }
            value = b*music[n] + tmp_value;
            if (value > max_value) max_value = value;
        }
    } else {
        for (b=max_bit; b >= 0; b--){
            if (b==0 && n>0) break;
            tmp_m = max_value_with_bits(m, b);
            if (tmp_m <= m_values[n]) continue;
            m_values[n] = tmp_m;
            if (n > 0) {
                tmp_value = optimise(music, N, tmp_m-1, t+1);
            } else {
                tmp_value = 0;
            }
            value = b*music[n] + tmp_value;
            if (value > max_value) max_value = value;
        }
    }
    max_values[n] = max_value;
    return max_value;
}

int main()
{
    int n, mb, i;
    LL m, result;
    LL music[MAX_LENGTH];
    cin >> n >> m;
    for (i=0; i < n; i++){
        cin >> music[i];
        m_values[i] = i;
        if (i == 0) max_values[i] = 0;
        else max_values[i] = music[i]*count_bits(i) + max_values[i-1];
    }
    result = optimise(music, n, m, 0);
    cout << result << endl;
    return 0;
}