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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 #include #include #include #include #include using namespace std; using I = unsigned long long; using LL = long long; inline int popcount(I a) { return __builtin_popcount(a >> 32) + __builtin_popcount(a & 0xFFFFFFFF); } inline I more_popcnt(I a, int l) { for (int i=0; i < 62; i++) { if (l == 0) return a; if(!(a & (1ull << i))) { a = a | (1ull << i); l --; } } abort(); } inline I less_popcnt(I a, int to) { int o = popcount(a); if (o <= 1) return (I)-1; for (int i=0; i < 62; i ++) { if (a & (1ull << i)) { a += 1ull << i; if (popcount(a) < o) return a; } } abort(); } I next_with_bits(I a, int bits) { while (true) { int b = popcount(a); if (b == bits) return a; else if (b < bits) return more_popcnt(a, bits - b); else a = less_popcnt(a, bits); if (a == (I)-1) return (I)-1; } } vector > hull(vector > pairs) { std::sort(pairs.begin(), pairs.end(), [](const pair& a, const pair& b) { return make_pair(a.second, -a.first) < make_pair(b.second, -b.first); }); LL min_y = numeric_limits::min(); vector > r; for (auto p : pairs) { I x = p.second; LL y = p.first; if (y > min_y) { r.push_back(make_pair(y, x)); min_y = y; } } return r; } LL solve(vector values, I limit) { vector> solutions; solutions.push_back(make_pair(0,0)); int max_popcnt = 62; for (LL v : values) { vector> new_solutions; for (auto sol : solutions) { LL price = sol.first; I minbit = sol.second; for (int target_popcnt=0; target_popcnt < max_popcnt; target_popcnt ++) { I cbit = next_with_bits(minbit, target_popcnt); if (cbit == (I)-1) continue; assert(popcount(cbit) == target_popcnt); //cout << cbit << " " << minbit << endl; assert(cbit >= minbit); if (cbit > limit) continue; LL new_price = target_popcnt * v + price; I new_minbit = cbit+1; new_solutions.push_back(make_pair(new_price, new_minbit)); } } //cerr << "presize " << new_solutions.size() << endl; solutions = hull(new_solutions); //cerr << "size " << solutions.size() << endl; } LL best_sol = numeric_limits::min(); for (auto sol : solutions) { best_sol = max(sol.first, best_sol); } return best_sol; } int main() { ios_base::sync_with_stdio(0); int n; I limit; cin >> n >> limit; vector values((size_t)n); for(LL&v:values)cin>>v; cout << solve(values, limit) << endl; }