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
105
106 | #include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 210, POT = 64;
const long long int INF = 1LL << 62;
long long int wyn[N][N][POT], a[N], pref[N];
void initialize(int n, int pot) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= pot; k++) {
wyn[i][j][k] = -INF;
//cerr << i << " " << j << " " << k << " " << wyn[i][j][k] << "\n";
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= pot; j++) {
wyn[i][i][j] = max(0LL, a[i] * j);
//cerr << i << " " << j << " " << wyn[i][i][j] << "\n";
}
}
}
long long int licz(int ap, int ak, int pot, long long int brak) {
if (brak == 0) {
if (wyn[ap][ak][pot] != -INF) {
//cerr << "A " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
return wyn[ap][ak][pot];
}
if (ak - ap + 1 > (1 << pot)) {
//cerr << "B " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
return -INF;
}
long long int best = -INF;
for (int i = ap; i < ak; i++) {
best = max(best,
licz(ap, i, pot - 1, 0)
+ licz(i + 1, ak, pot - 1, 0)
+ pref[ak] - pref[i]
);
}
wyn[ap][ak][pot] = best;
//cerr << "C " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
return best;
} else {
if (ak - ap + 1 > (1 << pot) - brak) {
//cerr << "B " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
return -INF;
}
if (brak >= (1LL << (pot - 1))) {
return licz(ap, ak, pot - 1, brak - (1LL << (pot - 1)));
}
long long int best = -INF;
for (int i = ap; i < ak; i++) {
best = max(best, licz(ap, i, pot - 1, 0)
+ licz(i + 1, ak, pot - 1, brak)
+ pref[ak] - pref[i]
);
}
wyn[ap][ak][pot] = best;
//cerr << "C " << ap <<":"<<ak<<" "<<pot<<" "<< wyn[ap][ak][pot] << "\n";
return best;
return 0;
}
}
int main() {
int n;
long long int m;
scanf("%d%lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
pref[i] = pref[i - 1] + a[i];
}
int pot = 0;
long long int xxx = 1;
while (xxx <= m) {
pot++;
xxx <<= 1;
}
//cerr << pot << " __ " << xxx << "\n";
initialize(n, pot);
long long int wynik = licz(1, n, pot, xxx - m - 1);
printf("%lld\n", wynik);
return 0;
}
|