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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef unsigned short u16;

static inline int PopCount(ull x)
{
	return __builtin_popcountll(x);
}

struct Cand {
	ll value;
	ull last_b;
	pair<ull, ll> Repr() const { return make_pair(last_b, -value); }
	bool operator<(const Cand& o) const { return Repr() < o.Repr(); }
};

void Prune(vector<Cand>& q)
{
	sort(q.begin(), q.end());
	int j = 1;
	for (int i = 1; i < (int) q.size(); i++)
		if (q[j - 1].value < q[i].value)
			q[j++] = q[i];
	q.resize(j);
}

int main()
{
	int n;
	ull m;
	scanf("%d%llu", &n, &m);
	vector<Cand> q;
	q.push_back(Cand{0, ~0ULL});
	while (n-- > 0)
	{
		ll a;
		scanf("%lld", &a);
		if (a == 0)
		{
			for (auto& c : q)
				c.last_b++;
			if (q.back().last_b > m)
				q.pop_back();
			continue;
		}
		vector<Cand> new_q;
		for (auto c : q)
		{
			c.last_b++;
			int k = PopCount(c.last_b);
			c.value += k * a;
			if (a > 0)
			{
				while (c.last_b <= m)
				{
					new_q.push_back(c);
					c.last_b |= c.last_b + 1;
					c.value += a;
				}
			}
			else
			{
				if (c.last_b > m)
					continue;
				new_q.push_back(c);
				while (k > 1)
				{
					c.last_b |= c.last_b - 1;
					c.last_b++;
					if (c.last_b > m)
						break;
					int l = PopCount(c.last_b);
					if (l < k)
					{
						c.value -= a * (k - l);
						k = l;
						new_q.push_back(c);
					}
				}
			}
			if (new_q.size() > 2000000)
				Prune(new_q);
		}
		q = move(new_q);
		Prune(q);
	}
	printf("%lld\n", q.back().value);
	return 0;
}