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 // {{{ #include #include #include #define VARGS_(_4, _3, _2, _1, N, ...) N #define VARGS(...) VARGS_(__VA_ARGS__, 4, 3, 2, 1) #define CONCAT_(a, b) a##b #define CONCAT(a, b) CONCAT_(a, b) #define FOR_1(x) for (auto& x) #define FOR_2(i, n) for (auto i = remove_reference_t{0}; i < (n); ++i) #define FOR_3(i, b, e) for (auto i = remove_reference_t{b}; i < (e); ++i) #define FOR_4(i, b, e, s) for (auto i = remove_reference_t{b}; i < (e); i += s) #define FORD_2(i, n) for (auto i = (n) - 1; i >= 0; --i) #define FORD_3(i, b, e) for (auto i = remove_reference_t{(e) - 1}; i >= (b); --i) #define FORD_4(i, b, e, s) for (auto i = remove_reference_t{(e) - 1}; i >= (b); i -= s) #define FOR(...) CONCAT(FOR_, VARGS(__VA_ARGS__))(__VA_ARGS__) #define FORD(...) CONCAT(FORD_, VARGS(__VA_ARGS__))(__VA_ARGS__) #define B begin() #define E end() #define RB rbegin() #define RE rend() #define A(x) std::begin(x), std::end(x) #define RA(x) std::rbegin(x), std::rend(x) #define RANGE(x, b, e) (std::begin(x) + (b)), (std::begin(x) + (e)) #define MP make_pair #define MT make_tuple #define FS first #define ND second #define G1 get<0> #define G2 get<1> #define G3 get<2> #define G4 get<3> #define G5 get<4> #define PB push_back #define PP pop_back #define PF push_front #define FF pop_front #define RS resize #define INF(T) numeric_limits::max() #define L0(_expr) [&]() { return _expr; } #define L1(_expr) [&](auto&& _1) { return _expr; } #define L2(_expr) [&](auto&& _1, auto&& _2) { return _expr; } #define _ CONCAT(_unused_, __COUNTER__) #define MIN min_element #define MAX max_element #define SUM accumulate using namespace std; using LL = long long; using LD = long double; using ULL = unsigned long long; template using P = pair; using PII = P; using PLL = P; using PLD = P; template using V = vector; using VI = V; using VLL = V; using VLD = V; using VB = V; using VS = V; template> using PQ = priority_queue,Comp>; template int sz(const T& x) { return size(x); } template bool amin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; } template bool amax(T& a, const T& b) { if (b > a) { a = b; return true; } return false; } /* find_by_order(k) - k'th largest counting from 0; order_of_key(k) - number of items strictly smaller than k; join(other), split(k, other) - all keys in other greater than in *(this). */ template> using ordered_map = __gnu_pbds::tree; template> using ordered_set = ordered_map; string _sep = " ", _ignore; bool _newline = true; stack _ostack; stack _istack; template void out(const TH& h) { if (_newline) _newline = false; else *_ostack.top() << _sep; *_ostack.top() << h; } template void out(const TH& h, const TA&... a) { out(h); out(a...); } void outln() { *_ostack.top() << '\n'; _newline = true; } template void outln(const TA&... a) { out(a...); outln(); } template void in(TH& h) { *_istack.top() >> h; } template void in(TH& h, TA&... a) { in(h); in(a...); } template void EXIT(const TA&... a) { outln(a...); exit(0); } #ifdef SPONGE template void dbg(const TA&... a) { _ostack.push(&cerr); cerr << "\033[1;33m"; outln(a...); cerr << "\033[0m"; _ostack.pop(); } #else #define dbg(...) #endif struct _upgrade_io { _upgrade_io(bool ok) { _ostack.push(&cout); _istack.push(&cin); if (ok) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed, ios::floatfield); }} } _upgrade_io(true); /* bitset: _Find_first(), _Find_next(i) */ // }}} int n, m; LL *dp; LL a[200]; int main() { in(n, m); FOR(i, n) in(a[i]); dp = new LL[m + 1]; fill(dp, dp + m + 1, 0); FOR(i, 1, m + 1) dp[i] = max(__builtin_popcount(i) * a[0], dp[i - 1]); FOR(k, 1, n) { FORD(i, k, m + 1) dp[i] = __builtin_popcount(i) * a[k] + dp[i - 1]; FOR(i, k + 1, m + 1) amax(dp[i], dp[i - 1]); } outln(dp[m]); }