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

int64_t MIN_VAL = -9223372036854775807;
int64_t MAX_VAL =  9223372036854775807;

using namespace std;

std::vector<int64_t> sums;

std::vector<int64_t> lookup (200*200*60, MIN_VAL);
std::vector<int64_t> lookup2 (200*200*5000, MIN_VAL);

int64_t dp(vector<int64_t> const& pops, int start, int end, int64_t max_numb){
    if(__builtin_popcountll(max_numb) == 1 && lookup[start* 200 * 60 + end * 60 + log2(max_numb)] != MIN_VAL){
        return lookup[start* 200 * 60 + end * 60 + log2(max_numb)];
    }
    if(max_numb < 5000 && lookup2[start* 200 * 5000 + end * 5000 + max_numb] != MIN_VAL){
        return lookup2[start* 200 * 5000 + end * 5000 + max_numb];
    }
    if(end == start){
        return 0;
    }
    if(end - start > max_numb){
        return MIN_VAL;
    }
    if(end - start == max_numb){
        int64_t ret = 0;
        int64_t counter = 0;
        for(int64_t i = start; i < end; i ++){
            ret += __builtin_popcountll(counter) * pops[i];
            counter ++;
        }
        return ret;
    }
    int64_t maxpow = 1;
    while(maxpow * 2 < max_numb){
        maxpow *= 2;
    }
    int64_t ret = MIN_VAL;
    for(int i = start; i <= end; i ++){
        int64_t sum = sums[i] - sums[end];
        int64_t left = dp(pops, start, i, maxpow);
        int64_t right = dp(pops, i, end, max_numb - maxpow);
        if(left != MIN_VAL && right != MIN_VAL){
            ret = max(ret, sum + left + right);
        }
    }
    if(__builtin_popcountll(max_numb) == 1){
        lookup[start* 200 * 60 + end * 60 + log2(max_numb)] = ret;
    }
    if(max_numb < 5000){
        lookup2[start* 200 * 5000 + end * 5000 + max_numb] = ret;
    }
    return ret;
}

int main(){

    int64_t n;
    int64_t m;
    cin >> n;
    cin >> m;

    vector<int64_t> pops;
    pops.reserve(n);

    int64_t sum = 0;
    sums.push_back(0);
    for(int i = 0; i < n; i++){
        int64_t tmp;
        cin >> tmp;
        sum += tmp;
        sums.push_back(sum);
        pops.push_back(tmp);
    }
    for(auto & cur: sums){
        cur = sum - cur;
    }
    m++;
    cout << dp(pops, 0, pops.size(), m) << endl;

}