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 #include #define ll long long #define mp make_pair #define pb push_back #define ld long double #define ss(x) (int) x.size() #define fi first #define se second #define cat(x) cout << #x << " = " << x << endl using namespace std; const int nax = 210; const ll inf = 1e18; const int LOG = 60; void maxi(ll &a, ll b) { a = max(a, b); } int n; ll m; ll a[nax]; ll p[nax]; ll dp[nax][nax][LOG + 1][2]; // dp[a][b][c][d] - przedzial [a, b], wynik jeśli mam jeszcze c bitów, d czy już liczby są mniejsze od M int kth[100]; int main() { scanf("%d %lld", &n, &m); for(int i = 1; i <= n; ++i) { scanf("%lld", a + i); p[i] = p[i - 1] + a[i]; } for(int i = 59; 0 <= i; --i) kth[i] = ((m >> i) & 1); for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) for(int k = 0; k <= LOG; ++k) for(int g = 0; g < 2; ++g) { dp[i][j][k][g] = -inf; if(k == 0) { if(i == j) dp[i][j][k][g] = 0; } } int bit, Left, Right, ile; for(bit = 1; bit <= LOG; ++bit) for(Left = 1; Left <= n; ++Left) for(Right = Left; Right <= n; ++Right) for(ile = 0; ile <= Right - Left + 1; ++ile) { maxi(dp[Left][Right][bit][0], dp[Left][Right - ile][bit - 1][0] + dp[Right - ile + 1][Right][bit - 1][0] + p[Right] - p[Right - ile]); if(!(kth[bit - 1] == 0 && ile > 0)) maxi(dp[Left][Right][bit][1], dp[Left][Right - ile][bit - 1][kth[bit - 1] == 0] + dp[Right - ile + 1][Right][bit - 1][1] + p[Right] - p[Right - ile]); } printf("%lld", dp[1][n][60][1]); //cerr << "Time = " << 1.0 * clock() / CLOCKS_PER_SEC << endl; return 0; }