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 <cstdio>
#include <vector>
#define P(x) (1ll<<(x))
using namespace std;
using LL = long long;
using VLL = vector<LL>;

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;
}