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 #include #define FOR(i, a, b) for (int i=(a); i<(b); i++) #define PPC(x) __builtin_popcountll((x)) #define ALL(x) (x).begin(), (x).end() #define pb push_back using namespace std; const int maxN = 222, B = 60; const long long INF = 3000000000000000000ll; template inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } long long sum[maxN][maxN], dp[maxN][maxN][B+1], dpfit[maxN][maxN][B+1]; int main() { int n; long long m; scanf ("%d%lld", &n, &m); FOR(i, 0, n) scanf ("%lld", &sum[i][i+1]); FOR(i, 0, n) FOR(j, i+2, n+1) { sum[i][j] = sum[i][j-1] + sum[j-1][j]; dp[i][j][0] = dpfit[i][j][0] = -INF; } FOR(len, 1, n+1) FOR(i, 0, n+1-len) FOR(b, 1, B+1) { int j = i + len; bool bit = (1ll << b-1) & m; dp[i][j][b] = dp[i][j][b-1]; dpfit[i][j][b] = bit ? dp[i][j][b-1] : dpfit[i][j][b-1]; if (len > (1ll << b)) continue; if (!bit) FOR(k, i, j) remax(dp[i][j][b], dp[i][k][b-1] + dp[k][j][b-1] + sum[k][j]); else FOR(k, i, j) { remax(dp[i][j][b], dp[i][k][b-1] + dp[k][j][b-1] + sum[k][j]); remax(dpfit[i][j][b], dp[i][k][b-1] + dpfit[k][j][b-1] + sum[k][j]); } } printf("%lld\n", dpfit[0][n][B]); return 0; }