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 #include using namespace std; using ll = long long; const ll INF = ll(1e18) * 3LL; int n; ll m; ll a[207]; ll pref[207]; ll mem[207][207][2][67]; bool vis[207][207][2][67]; // t: // 0 - 2^k-1 // 1 - k ostatnich cyfr m ll calc(int a, int b, int t, int k) { if(vis[a][b][t][k]) return mem[a][b][t][k]; if(b < a) return 0; if(k == -1) { if(a == b) return 0; else return -INF; } vis[a][b][t][k] = 1; mem[a][b][t][k] = -INF; int l = k - 1; while(l >= 0 && !(m & (1LL << l))) l--; for(int d = a - 1 ; d <= b ; d++) { ll tmp = calc(a, d, 0, k - 1); if(t == 0) tmp += calc(d + 1, b, 0, k - 1); else tmp += calc(d + 1, b, 1, l); tmp += pref[b] - pref[d]; mem[a][b][t][k] = max(mem[a][b][t][k], tmp); } return mem[a][b][t][k]; } int main() { scanf("%d%lld", &n, &m); for(int i = 1 ; i <= n ; i++) { scanf("%lld", &a[i]); pref[i] = pref[i - 1] + a[i]; } int x = 61; while(x >= 0 && !(m & (1LL << x))) x--; printf("%lld\n", calc(1, n, 1, x)); return 0; }