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 #include using namespace std; const int MAXN = 210; const int MAXB = 64; using ll = long long int; const ll INF = 1000000000000000000LL; ll a[MAXN]; ll DP[MAXB][MAXN][MAXN][2]; //DP[l][r][b][md] - najlepszy koszt ciągu (a_l, ..., a_r) gdzie b_i nale¿y do przedziału: //md = 0 -> (0, 2 ** b - 1) //md = 1 -> (0, (2 ** b - 1) & m) ll sum[MAXN][MAXN]; //sum[l][r] = a_l + a_{l+1} + ... + a_{r-1} + a_r int llog(ll m) { int ret = 0; ll p = 1; while (m >= p) { p *= 2; ret++; } return ret; } int main() { int n; ll m; scanf("%d%lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (int l = 1; l <= n; l++) { sum[l][l] = a[l]; for (int r = l + 1; r <= n; r++) { sum[l][r] = sum[l][r - 1] + a[r]; } } for (int l = 1; l <= n; l++) { for (int r = l + 1; r <= n; r++) { DP[0][l][r][0] = -INF; DP[0][l][r][1] = -INF; } } for (int b = 1; b <= llog(m); b++) { bool mm = (m & (1LL << (b - 1))); if (mm) { for (int l = 1; l <= n; l++) { for (int r = l; r <= n; r++) { DP[b][l][r][0] = DP[b - 1][l][r][0] + max(0LL, sum[l][r]); DP[b][l][r][1] = max(DP[b - 1][l][r][0], DP[b - 1][l][r][1] + sum[l][r]); for (int t = l; t < r; t++) { DP[b][l][r][0] = max(DP[b][l][r][0], DP[b - 1][l][t][0] + DP[b - 1][t + 1][r][0] + sum[t + 1][r]); DP[b][l][r][1] = max(DP[b][l][r][1], DP[b - 1][l][t][0] + DP[b - 1][t + 1][r][1] + sum[t + 1][r]); } } } } else { for (int l = 1; l <= n; l++) { for (int r = l; r <= n; r++) { DP[b][l][r][0] = DP[b - 1][l][r][0] + max(0LL, sum[l][r]); DP[b][l][r][1] = DP[b - 1][l][r][1]; for (int t = l; t < r; t++) { DP[b][l][r][0] = max(DP[b][l][r][0], DP[b - 1][l][t][0] + DP[b - 1][t + 1][r][0] + sum[t + 1][r]); } } } } } printf("%lld\n", DP[llog(m)][1][n][1]); }