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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
#define ll long long
#define debug if(0)

const int MAX_N = 200;
const int MAX_LOG = 60;
int n; ll m;
ll a[MAX_N+3];
ll pref[MAX_N+3];
ll potega[MAX_LOG+3];
const ll inf = LLONG_MAX;

void input(){
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];
    pref[0] = 0;
    for (int i = 1; i <= n; i++)
        pref[i] = (pref[i-1] + a[i]);
    potega[0] = 1;
    for (int i = 1; i <= MAX_LOG+1; i++)
        potega[i] = (potega[i-1] * (ll)(2));
}

ll sum(int i, int j){
    return pref[j] - pref[i-1];
}

ll dpI[MAX_LOG+3][MAX_N+3][MAX_N+3];
int max_k;
void count_dp_1(){
    ll pot = 1; int wyk = 0;
    while (pot * 2 - 1 <= 2*m){
        pot *= 2;
        wyk++;
    }
    max_k = wyk;
    // dpI[k][i][j] to max wynik dla przedzialu [i, j] z liczbami z przedzialu [0, 2^k)
    // najpierw i == j
    for (ll k = 0; k <= max_k; k++){
        for (int i = 1; i <= n; i++){
            if (a[i] > 0)
                dpI[k][i][i] = k * a[i];
            else if (a[i] <= 0)
                dpI[k][i][i] = 0;
            debug std::cout << "dpI[" << k << "][" << i << "][" << i << "] = " << dpI[k][i][i] << "\n";
        }
    }
    // teraz dluzsze przedzialy
    for (ll k = 0; k <= max_k; k++){
        for (int len = 2; len <= n; len++){
            for (int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                dpI[k][i][j] = -inf;
                if (len > potega[k]){
                    debug std::cout << len << " jest wiekszy od " << potega[k] << ", stad dpI[" << k << "][" << i << "][" << j << "] = " << dpI[k][i][j] << "\n";
                    continue;
                }
                for (int l = i+1; l <= j; l++){
                    // przedzial [i, l-1] realizuje w [0, 2^(k-1)) a przedzial [l, j] w [2^(k-1), 2^k)
                    // czyli tak naprawde przedzial pierwszy faktycznie realizuje tak jak napisalem
                    // a drugi w przedziale tez [0, 2^(k-1)] ale zawsze musze doliczyc jeden bit, czyli sume na tym przedziale
                    if (dpI[k-1][i][l-1] > -inf && dpI[k-1][l][j] > -inf)
                        dpI[k][i][j] = std::max(dpI[k][i][j], dpI[k-1][i][l-1] + dpI[k-1][l][j] + sum(l, j));
                }
                debug std::cout << "dpI[" << k << "][" << i << "][" << j << "] = " << dpI[k][i][j] << "\n";
            }
        }
    }
}

ll dpII[MAX_LOG+3][MAX_N+3];
void count_dp_2(){
    // ten dp jest tricky
    ll pot = 1; ll wyk = 0;
    while (pot * 2 <= m+1){
        pot *= 2;
        wyk++;
    }
    ll M = m+1;
    std::vector<int> pots;
    pots.push_back(-1);
    while (M > 0){
        if (pot <= M){
            pots.push_back(wyk);
            M -= pot;
        }
        pot /= 2;
        wyk--;
    }

    debug{
        std::cout << "M+1 = " << m+1 << " = ";
        for (int i = 1; i < pots.size(); i++){
            std::cout << "2^" << pots[i] << " + " << " ";
        }
        std::cout << "\n";
    }
    // mam m+1 = 2^(a_1) + 2^(a_2) + 2^(a_3) + ... + 2^(a_k)
    // gdzie a_1 > a_2 > a_3 > ... > a_k
    // i teraz definiuje dp:
    // dp[k][i] = wynik dla prefiksu 1..i z wartosciami z przedzialu [0, 2^(a_1) + 2^(a_2) + .. + 2^(a_k))
    for (int i = 1; i <= n; i++)
        dpII[0][i] = -inf;
    dpII[0][0] = 0;
    for (ll k = 1; k < pots.size(); k++){
        int h = pots[k];
        for (int i = 1; i <= n; i++){
            dpII[k][i] = -inf;
            for (int j = i-1; j >= 0; j--){
                // prefiks 1..j ma byc zrealizowany w przedziale [0, 2^(a_1) + ... + 2^(a_(k-1)))
                // a przedzial [j+1, i] w przedziale [2^(a_1) + ... + 2^(a_k-1), 2^(a_1) + ... + 2^(a_k))
                // czyli tak naprawde uzywam liczb z przedzialu [0, 2^(a_k)) i dodaje k-1 bitow, czyli k-1 * suma(j+1, i)
                if (dpII[k-1][j] > -inf && dpI[h][j+1][i] > -inf)
                    dpII[k][i] = std::max(dpII[k][i], dpII[k-1][j] + dpI[h][j+1][i] + (k-1)*sum(j+1, i));
            }
            if (k >= 2 && dpII[k-1][i] > -inf)
                dpII[k][i] = std::max(dpII[k][i], dpII[k-1][i]);
            debug std::cout << "dpII[" << k << "][" << i << "] = " << dpII[k][i] << "\n";
        }
    }
    int tmp = pots.size();
    debug std::cout << "Wynik zczytuje z dpII[" << tmp-1 << "][" << n << "]\n";
    std::cout << dpII[tmp-1][n] << "\n";
}

int main(){
    std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
    input();
    count_dp_1();
    count_dp_2();
}