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

using namespace std;

const int N = 210, POT = 64;
const long long int INF = 1LL << 62;

long long int wyn[N][N][POT], a[N], pref[N];

void initialize(int n, int pot) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k <= pot; k++) {
                wyn[i][j][k] = -INF;
                //cerr << i << " " << j << " " << k << " " << wyn[i][j][k] << "\n";

            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= pot; j++) {
            wyn[i][i][j] = max(0LL, a[i] * j);
            //cerr << i << " " << j << " " << wyn[i][i][j] << "\n";
        }
    }
}

long long int licz(int ap, int ak, int pot, long long int brak) {
    if (brak == 0) {
        if (wyn[ap][ak][pot] != -INF) {
            //cerr << "A " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
            return wyn[ap][ak][pot];
        }
        if (ak - ap + 1 > (1 << pot)) {
            //cerr << "B " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
            return -INF;
        }
        
        long long int best = -INF;
        for (int i = ap; i < ak; i++) {
            best = max(best,
                       licz(ap, i, pot - 1, 0)
                        + licz(i + 1, ak, pot - 1, 0)
                        + pref[ak] - pref[i]
                      );
        }
        
        wyn[ap][ak][pot] = best;
        //cerr << "C " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
        return best;
        
    } else {
        if (ak - ap + 1 > (1 << pot) - brak) {
            //cerr << "B " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
            return -INF;
        }
        
        if (brak >= (1LL << (pot - 1))) {
            return licz(ap, ak, pot - 1, brak - (1LL << (pot - 1)));
        }
        
        long long int best = -INF;
        for (int i = ap; i < ak; i++) {
            best = max(best, licz(ap, i, pot - 1, 0)
                        + licz(i + 1, ak, pot - 1, brak)
                        + pref[ak] - pref[i]
                      );
        }
        
        wyn[ap][ak][pot] = best;
        //cerr << "C " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
        return best;
        
        return 0;
    }
}

int main() {
    int n;
    long long int m;
    scanf("%d%lld", &n, &m);
    
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        pref[i] = pref[i - 1] + a[i];
    }
    
    int pot = 0;
    long long int xxx = 1;
    while (xxx <= m) {
        pot++;
        xxx <<= 1;
    }
    
    //cerr << pot << " __ " << xxx << "\n";
    
    initialize(n, pot);
    long long int wynik = licz(1, n, pot, xxx - m - 1);
    
    printf("%lld\n", wynik);

    return 0;
}