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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4000000000000000000;
ll n, k;
ll a[210];
ll dp[210][210][64];
ll pref[210];
ll itEnds[210][210][64];
vector<int> atoms;
inline ll sum(int a, int b)
{
    return pref[b] - pref[a - 1];
}

inline ll lsb(ll x)
{
    return x & (-x);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    ++k;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    for(int l = 1; l <= n; ++l) for(int r = 1; r <= n; ++r) for(int x = 0; x < 64; ++x) dp[l][r][x] = -INF;
    for(int l = 1; l <= n; ++l) for(ll x = 0; x < 64; ++x) dp[l][l][x] = x * max(0ll, a[l]);
    for(int x = 1; x < 64; ++x)
    {
        for(int l = 1; l <= n; ++l) for(int r = l; r <= n; ++r)
        {
            ll writeVal = -INF;
            for(int m = l - 1; m + 1 <= r; ++m)
            {
                writeVal = max(writeVal, dp[l][m][x - 1] + dp[m + 1][r][x - 1] + sum(m + 1, r));
            }
            for(int y = x; y < 64; ++y)
            {
                dp[l][r][y] = max(dp[l][r][y], writeVal);
            }
        }
    }
    /*for(int l = 1; l <= n; ++l)
    {
        for(int r = l; r <= n; ++r)
        {
            cout << l << ' ' << r << ' ';
            for(int x = 0; x <= 3; ++x)
            {
                cout << dp[l][r][x] << ' ';
            }
            cout << '\n';
        }
    }*/
    while(k)
    {
        ll u = lsb(k);
        atoms.push_back(__lg(u));
        //cout << __lg(u) << ' ';
        k -= u;
    }
    //cout << '\n';
    reverse(atoms.begin(), atoms.end());
    for(int r = 1; r <= n; ++r)
    {
        itEnds[1][r][1] = dp[1][r][atoms[0]];
    }
    for(int x = 2; x <= atoms.size(); ++x)
    {
        for(int r = 1; r <= n; ++r)
        {
            ll writeVal = max(-INF, itEnds[1][r][x - 1] + sum(r + 1, n));
            for(int m = 0; m + 1 <= r; ++m)
            {
                writeVal = max(writeVal, itEnds[1][m][x - 1] + dp[m + 1][r][atoms[x - 1]] + sum(m + 1, n));
            }
            itEnds[1][r][x] = writeVal;
        }
    }
    /*for(int r = 1; r <= n; ++r)
        {
            cout << r << ' ';
            for(int x = 0; x <= 3; ++x)
            {
                cout << itEnds[1][r][x] << ' ';
            }
            cout << '\n';
        }*/
    cout << itEnds[1][n][atoms.size()] << '\n';
    //cout << dp[1][n][2];
    return 0;
}