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

using namespace std;

typedef long long lng;
typedef vector<lng> vl;

const lng inf = 9e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    lng m;
    cin >> n >> m;

    vl a(n);
    for (lng& x : a)
        cin >> x;

    vl d(m+1, 0);

    for (lng x = 1; x <= m; x++) {
        int b = __builtin_popcount(x);
        d[x] = max(d[x-1], b * a[0]);
    }

    for (int i = 1; i < n; i++) {
        vl p(m+1, -inf);

        for (lng x = i; x <= m; x++) {
            int b = __builtin_popcount(x);
            p[x] = max(p[x-1], b * a[i] + d[x-1]);
        }

        d = p;
    }

    cout << d.back() << "\n";

    return 0;
}