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 #include #include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define INT(x) int x; scanf("%d", &x) #define LLG(x) LL x; scanf("%lld", &x) typedef long long LL; const LL INF = 8000000000000000000LL; LL a[200], s[201]; LL res[201][201][61], resm[201][201][61]; int main() { INT(n); LLG(m); REP(i,n) scanf("%lld", &a[i]); s[0] = 0; REP(i,n) s[i + 1] = s[i] + a[i]; REP(i,n+1) FOR(j,i,n+1) REP(k,61) res[i][j][k] = resm[i][j][k] = -INF; REP(i,n+1) REP(k,61) res[i][i][k] = resm[i][i][k] = 0; REP(i,n) res[i][i + 1][0] = resm[i][i + 1][0] = 0; FOR(d,1,n+1) REP(i,n-d+1) { int j = i + d; FOR(k,1,61) { LL r = -INF; FOR(x,i,j+1) if (res[i][x][k - 1] > -INF && res[x][j][k - 1] > -INF) r = max(r, res[i][x][k - 1] + res[x][j][k - 1] + s[j] - s[x]); res[i][j][k] = r; if (!(m & (1LL << (k - 1)))) { resm[i][j][k] = resm[i][j][k - 1]; continue; } r = -INF; FOR(x,i,j+1) if (res[i][x][k - 1] > -INF && resm[x][j][k - 1] > -INF) r = max(r, res[i][x][k - 1] + resm[x][j][k - 1] + s[j] - s[x]); resm[i][j][k] = r; } } printf("%lld\n", resm[0][n][60]); }