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 #include #include #define P(x) (1ll<<(x)) using namespace std; using LL = long long; using VLL = vector; const int N = 200; const int M = 60; const LL NAN = -LL(1e18)-1; LL n, m, a[N+1], d[M+1][N][N+1]; LL sum(int i, int j) { return a[i] - a[j]; } int main() { scanf("%lld%lld", &n, &m); for (int i = 0; i < n; ++i) scanf("%lld", &a[i]); for (int i = n-1; i >= 0; --i) a[i] += a[i+1]; for (int i = 0; i < n; ++i) for (int j = i+2; j <= n; ++j) { d[0][i][j] = NAN; // switch (j - i) { // case 1: d[1][i][j] = max(0ll, sum(i, j)); break; // case 2: d[1][i][j] = sum(i + 1, j); break; // default: d[1][i][j] = NAN; // } } VLL e(N+1, NAN), ep(N+1); e[n-1] = e[n] = 0; for (int p = 0; P(p) <= m; ++p) { if (p) { for (int i = 0; i < n; ++i) for (int j = i+1; j <= n; ++j) { LL x = NAN; for (int k = i; k <= j; ++k) if (d[p-1][i][k] != NAN && d[p-1][k][j] != NAN) x = max(x, d[p-1][i][k] + sum(k, j) + d[p-1][k][j]); d[p][i][j] = x; } } if (m & P(p)) { // for (int i = 0; i<=n; ++i) printf("%lld ", e[i]); // puts(""); ep.swap(e); for (int i = 0; i < n; ++i) { e[i] = NAN; for (int j = i; j <= n; ++j) if (d[p][i][j] != NAN && ep[j] != NAN) e[i] = max(e[i], d[p][i][j] + sum(j, n) + ep[j]); } } } // printf("%lld %lld %lld\n", d[1][0][1], sum(1, 3), ep[1]); printf("%lld\n", e[0]); return 0; }