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
#include <bits/stdc++.h>

using namespace std;

const int64_t oo = INT64_MAX / 5;
const size_t NAX = 256, BITS = 64;

template<typename T>
T read(istream& in = cin) { T x; in >> x; return x; }

int main()
{
    const size_t n = read<size_t>();
    const int64_t m = read<int64_t>();

    static int64_t A[NAX];
    for(size_t i = 0; i < n; i++)
        cin >> A[i];

    if(m == 0) { cout << 0; return 0; }

    static int64_t B[BITS][NAX][NAX][2];

    const size_t bits = __lg(m);

    for(size_t i = 0; i < n; i++)
      for(size_t j = i+1; j <= n; j++)
    {
        auto& b = B[0][i][j];
        if(j-i > 2)
            b[0] = b[1] = -oo;
        else
        {
            if(j-i == 2)
                b[0] = A[i+1], b[1] = (m & 1) ? b[0] : -oo;
            else
                b[0] = max((int64_t)0, A[i]), b[1] = (m & 1) ? b[0] : 0;
        }
    }

    for(size_t k = 1; k <= bits; k++)
      for(size_t i = 0; i < n; i++)
        for(size_t j = i+1; j <= n; j++)
    {
        auto &b = B[k][i][j];

        b[0] = b[1] = -oo;

        b[1] = max(b[1], B[k-1][i][j][1]);
        int64_t sum = -A[j];
        for(size_t l = j+1; l --> i; )
        {
            sum += A[l];
            b[0] = max(b[0], B[k-1][i][l][0] + B[k-1][l][j][0] + sum);
            if(m >> k & 1)
                b[1] = max(b[1], B[k-1][i][l][0] + B[k-1][l][j][1] + sum);
        }
    }
    cout << B[bits][0][n][true];
}