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 97 #include #include #include #include using namespace std; namespace { using ll = long long; constexpr auto inf = std::numeric_limits::max(); ll plus(ll a, ll b) { if (a <= -inf || b <= -inf) return -inf; return a + b; } ll plus(ll a, ll b, ll c) { return plus(a, plus(b, c)); } ll solve(vector const& data, ll m) { int n = data.size(); vector psum(n + 1); psum[0] = 0; for (int i = 0; i < n; ++i) { psum[i + 1] = psum[i] + data[i]; } auto sum = [&](int l, int r) { return psum[r] - psum[l]; }; int B = 0; while ((1LL << B) - 1 < m) ++B; vector>> tmp(n + 1, vector>(n + 1, vector(B + 1, -inf))); for (int i = 0; i <= n; ++i) { for (int b = 0; b <= B; ++b) { tmp[i][i][b] = 0; } if (i < n) tmp[i][i+1][0] = 0; } for (int d = 1; d <= n; ++d) { for (int l = 0; l <= n - d; ++l) { int r = l + d; for (int b = 1; b <= B; ++b) { auto& dest = tmp[l][r][b]; dest = tmp[l][r][b - 1]; for (int c = l; c <= r; ++c) { dest = max(dest, plus(tmp[l][c][b-1], tmp[c][r][b-1], sum(c, r))); } } } } vector> res(n + 1, vector(B + 1, -inf)); for (int b = 0; b <= B; ++b) res[n][b] = 0; if (n > 0) res[n-1][0] = 0; for (int l = n; l >= 0; --l) { for (int b = 1; b <= B; ++b) { auto& dest = res[l][b]; dest = res[l][b - 1]; if ((m & (1LL << (b - 1))) == 0) continue; for (int c = l; c <= n; ++c) { dest = max(dest, plus(tmp[l][c][b-1], res[c][b-1], sum(c, n))); } } } return res[0][B]; // XXX, końcówka } } int main() { iostream::sync_with_stdio(false); cin.tie(nullptr); int n; ll m; cin >> n >> m; vector data(n); for (auto& x: data) cin >> x; cout << solve(data, m) << endl; return 0; }