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
#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <utility>
#include <vector>

#ifdef _MSC_VER
#include <intrin.h>
#define popcount __popcnt64
#else
#define popcount __builtin_popcountll
#endif

void insert_if_greater(std::map<unsigned long long, long long>& m, unsigned long long k, long long v) {
	auto it = m.lower_bound(k);
	if (it != m.end() && it->first == k) {
		if (it->second < v) {
			it->second = v;
		}
		return;
	}
	if (it != m.begin() && std::prev(it)->second >= v)
		return;
	m.emplace_hint(it, k, v);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	unsigned long long m;
	std::cin >> n >> m;
	std::map<unsigned long long, long long> best {{0, 0}};
	while (n--) {
		std::map<unsigned long long, long long> next;
		long long a;
		std::cin >> a;
		for (const auto& [b, r] : best) {
			if (a < 0) {
				decltype(popcount(0uLL)) q = 65;
				for (auto c = b; c + n <= m && q > 1; c += c & ~(c - 1)) {
					auto p = popcount(c);
					if (p < q) {
						insert_if_greater(next, c + 1, r + a * p);
						q = p;
					}
				}
			} else if (a > 0) {
				auto p = popcount(b);
				for (auto c = b; c + n <= m; c |= c + 1, p++) {
					insert_if_greater(next, c + 1, r + a * p);
				}
			} else if (b + n <= m) {
				insert_if_greater(next, b + 1, r);
			}
		}
		for (auto it = next.begin(); it != next.end(); ++it) {
			while (std::next(it) != next.end() && std::next(it)->second <= it->second) {
				next.erase(std::next(it));
			}
		}
		best = std::move(next);
	}
	std::cout << best.rbegin()->second << '\n';
	return 0;
}