#include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> using namespace std; typedef long long ll; const int N = 61; const int M = 201; ll dp[N][2][M][M]; int n; ll m; ll a[M]; ll pref[M]; string s; const ll inf = (ll) (1e18); ll f(int l, int r) { if (l > r) return 0; if (!l) return pref[r]; else return pref[r] - pref[l - 1]; } ll calc(int i, int t, int l, int r) { if (dp[i][t][l][r] != -1) return dp[i][t][l][r]; if (l > r) return 0; if (i == 60) { if (l != r) return -inf; return 0; } else { ll val = -inf; for (int x = l - 1; x <= r; x++) { if (1 > s[i] && !t && (x != r)) { continue; } ll a = calc(i + 1, ((0 < s[i]) || t), l, x); ll b = calc(i + 1, t, x + 1, r) + f(x + 1, r); val = max(val, a + b); } return dp[i][t][l][r] = val; } } int main() { #ifdef iq freopen("a.in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; ll ret = 0; for (int i = 0; i < n; i++) { cin >> a[i]; ret += a[i]; pref[i] = ret; } for (int it = 0; it < 60; it++) { s += (m % 2); m /= 2; } for (int it = 0; it <= 60; it++) { for (int t = 0; t < 2; t++) { for (int l = 0; l <= n; l++) { for (int r = 0; r <= n; r++) { dp[it][t][l][r] = -1; } } } } reverse(s.begin(), s.end()); cout << calc(0, 0, 0, n - 1) << endl; }
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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> using namespace std; typedef long long ll; const int N = 61; const int M = 201; ll dp[N][2][M][M]; int n; ll m; ll a[M]; ll pref[M]; string s; const ll inf = (ll) (1e18); ll f(int l, int r) { if (l > r) return 0; if (!l) return pref[r]; else return pref[r] - pref[l - 1]; } ll calc(int i, int t, int l, int r) { if (dp[i][t][l][r] != -1) return dp[i][t][l][r]; if (l > r) return 0; if (i == 60) { if (l != r) return -inf; return 0; } else { ll val = -inf; for (int x = l - 1; x <= r; x++) { if (1 > s[i] && !t && (x != r)) { continue; } ll a = calc(i + 1, ((0 < s[i]) || t), l, x); ll b = calc(i + 1, t, x + 1, r) + f(x + 1, r); val = max(val, a + b); } return dp[i][t][l][r] = val; } } int main() { #ifdef iq freopen("a.in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; ll ret = 0; for (int i = 0; i < n; i++) { cin >> a[i]; ret += a[i]; pref[i] = ret; } for (int it = 0; it < 60; it++) { s += (m % 2); m /= 2; } for (int it = 0; it <= 60; it++) { for (int t = 0; t < 2; t++) { for (int l = 0; l <= n; l++) { for (int r = 0; r <= n; r++) { dp[it][t][l][r] = -1; } } } } reverse(s.begin(), s.end()); cout << calc(0, 0, 0, n - 1) << endl; } |