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 #include using namespace std; typedef long long ll; const ll inf = 1000000000000000001; const int N = 205; const int B = 61; int n, i, k, a, b; ll m; ll t [N]; ll p [N]; ll dp1 [N][N][2]; ll dp2 [N][N][2]; inline ll sum (const int& a, const int& b) { return p[b] - p[a-1]; } inline void relax (ll& a, const ll& b) { if (b <= -inf) return; if (a < b) a = b; } int main () { scanf ("%d%lld", &n, &m); for (i=1; i<=n; i++) { scanf ("%lld", &t[i]); p[i] = p[i-1] + t[i]; } for (a=1; a<=n; a++) for (b=a+1; b<=n; b++) { dp2[a][b][0] = -inf-inf; dp2[a][b][1] = -inf-inf; } for (k=1; k<=B; k++) { for (a=1; a<=n; a++) for (b=a; b<=n; b++) { dp1[a][b][1] = dp2[a][b][1]; for (i=a; i<=b; i++) relax(dp1[a][b][1], dp2[a][i-1][1] + dp2[i][b][1] + sum(i, b)); dp1[a][b][0] = dp2[a][b][0]; if (((m>>(k-1))&1ll) == 0) continue; dp1[a][b][0] = dp2[a][b][1]; for (i=a; i<=b; i++) relax(dp1[a][b][0], dp2[a][i-1][1] + dp2[i][b][0] + sum(i, b)); } for (a=1; a<=n; a++) for (b=a; b<=n; b++) { dp2[a][b][0] = dp1[a][b][0]; dp2[a][b][1] = dp1[a][b][1]; } } printf ("%lld\n", dp2[1][n][0]); return 0; }