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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 `// Artur Kraska, II UWr #include #define forr(i, n) for(int i=0; i=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 2000000000000000007LL using namespace std; int n; long long tab[66][207][207], m, a, t[207], sum[207], res[207]; long long suma(int p, int k) { return sum[k] - sum[p-1]; } int main() { /*forr(i, 307) { if(i%8 == 0) cout << endl << i << " -> "; cout << __builtin_popcount(i) << " "; }*/ scanf("%d %lld", &n, &m); m++; FOR(i, 1, n) { scanf("%lld", &t[i]); sum[i] = t[i] + sum[i-1]; } long long ile = 0, m2 = m; while(m2 > 0) { m2 /= 2; ile++; } ile--; // sprawdzic m=0 FOR(i, 1, n) { tab[0][i][i] = 0; FOR(j, i+1, n) tab[0][i][j] = -INF; } //cout << ile << endl; FOR(d, 1, ile) { FOR(i, 1, n) { tab[d][i][i-1] = 0; FOR(j, i, n) { tab[d][i][j] = -INF; FOR(k, i-1, j) { tab[d][i][j] = max(tab[d][i][j], tab[d-1][i][k] + tab[d-1][k+1][j] + suma(k+1, j)); } //cout << "tab[" << i << "][" << j << "][" << d << "] = " << tab[i][j][d] << endl; } } tab[d][n+1][n] = 0; } FOR(i, 1, n) res[i] = -INF; res[n+1] = 0; FOR(d, 0, ile) { if((m & (1LL<