#include <bits/stdc++.h>
template <class X, class Y>
bool cmax(X &a, const Y &b) {
return a < b ? a = b, 1 : 0;
}
using namespace std;
using ll = long long;
const int N = 100005, K = 205;
ll S[N], Dp[K][N], Opt[K][N];
void Dnc(int k, int l, int r, int optl, int optr) {
int m = (l + r) / 2;
for (int i = optl; i <= min(m, optr); i++)
if (cmax(Dp[k][m], Dp[k - 1][i - 1] +
S[i - 1] * (S[m] - S[i - 1]))) Opt[k][m] = i;
if (l < m) Dnc(k, l, m - 1, optl, Opt[k][m]);
if (m < r) Dnc(k, m + 1, r, Opt[k][m], optr);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k; k++;
for (int i = 1; i <= n; i++) {
cin >> S[i]; S[i] += S[i - 1];
}
memset(Dp, 0xc0, sizeof Dp); Dp[0][0] = 0;
for (int i = 1; i <= k; i++) Dnc(i, i, n, i, n);
cout << Dp[k][n] << '\n'; stack <int> splits;
while (Opt[k][n] > 1) {
n = Opt[k][n]; k--; splits.push(n);
}
while (splits.size()) {
cout << splits.top() << ' '; splits.pop();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
75 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
73 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
70 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
73 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
71 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
81 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |