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 `#include using namespace std; typedef long long ll; long long m, a[210], dp[210][210][68][2], pref[210]; bool used[210][210][68][2]; int n; ll rec(int l, int r, int deep, int suff){ if (l > r) return 0; if (used[l][r][deep+1][suff]){ return dp[l][r][deep+1][suff]; } if (deep == -1){ return dp[l][r][deep+1][suff] = 0; } used[l][r][deep+1][suff] = 1; dp[l][r][deep+1][suff] = -1e18; for (int i = l-1; i <= r; i++){ int l1 = l, r1 = i; int l2 = i+1, r2 = r; bool bb = 1; if (r1-l1+1 > (1ll<<(ll)(deep))){ bb = 0; } if (suff == 0){ if (r2-l2+1 > (1ll<<(ll)(deep))) bb = 0; } else { if (((m & (1ll<<(ll)(deep))) == 0 && l2 <= r2 )|| r2-l2+1 > m-(1ll<<(ll)(deep))+1) bb = 0; } if (bb == 0){ continue; } dp[l][r][deep+1][suff] = max(dp[l][r][deep+1][suff], rec(l1, r1, deep-1, 0)+rec(l2, r2, deep-1, suff)+pref[r2]-pref[l2-1]); //cout << l << ' ' << r << ' ' << i << ' ' << deep << ' ' << suff << ' ' << rec(l1, r1, deep-1, 0) << ' ' << rec(l2, r2, deep-1, suff) << ' ' << pref[r2]-pref[l2-1] << endl; } return dp[l][r][deep+1][suff]; } int main(int argc, char *argv[]){ cin >> n >> m; for (int i = 1; i <= n; i++){ cin >> a[i]; pref[i] = pref[i-1] + a[i]; } ll mxbt = 0; for (ll bt = 0; bt < 63; bt++){ if ((1ll<