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 using namespace std; #define FOR(i, a, n) for(decltype(n) i = (a), i##__ = (n); i <= i##__; i++) #define REP(i, n) FOR(i, 0, (n)-1) #define FORD(i, a, n) for(decltype(a) i = (a), i##__ = (n); i >= i##__; i--) #define REPD(i, n) FORD(i, (n)-1, 0) #define V vector #define RS resize #define EB emplace_back #define ALL(X) X.begin(), X.end() #define SZ(X) int(X.size()) #define OS ostream #define ST first #define ND second using VI = V; using VVI = V; using II = pair; using VII = V; using L = long long; using VL = V; using VVL = V; constexpr L inf = 1e18; #ifdef DEBUG # define D(a...) a #else # define D(a...) #endif # define I(a...) #a << ": " << a << "\n" template OS& operator<<(OS &os, pair &X) { return os << "(" << X.ST << ", " << X.ND << ")"; } template OS& operator<<(OS &os, V &X){ os << "{"; REP(i, SZ(X)) os << X[i] << ((i == SZ(X) - 1) ? "" : ", "); return os << "}"; } template OS& operator<<(OS &os, V> &X) { os << "[\n"; for(auto &x : X) cout << " " << x << "\n"; return os << "]"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; VL a(n); REP(i, n) cin >> a[i]; VVL dp(n + 1, VL(m + 1, -inf)); dp[0] = VL(m + 1, 0); dp[1][0] = 0; FOR(i, 1, n) FOR(j, 1, m) { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + __builtin_popcount(j) * a[i - 1]); if(dp[i][j] < -4e17) dp[i][j] = -inf; } D(cerr << I(dp)); cout << dp[n][m] << "\n"; }