#include <bits/stdc++.h>
using namespace std;
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }
#define int long long
const int mxk = 22;
const int mxn = 1010;
const int gay = -100;
int dp[mxn][mxk], a[mxn], n;
int ls[mxn][mxk], p[mxn], k;
signed main() {
cin >> n >> k;
if(n > mxn) return 1;
for(int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++) {
dp[i][j] = gay;
if(j == 0)
dp[i][j] = p[i] * p[i];
}
for(int cur = 2; cur <= n; cur++)
for(int las = 1; las < cur; las++) {
int las_sum = p[cur] - p[las];
for(int j = 0; j < k && dp[las][j] != gay; j++) {
int CMP = dp[las][j] + las_sum * las_sum;
if(dp[cur][j + 1] == gay || dp[cur][j + 1] > CMP) {
dp[cur][j + 1] = CMP;
ls[cur][j + 1] = las;
}
}
}
int t = (p[n] * p[n] - dp[n][k]) / 2;
cout << t << endl;
vector<int> v;
for(int i = k; i >= 0; i--) {
// v.push_back(n);
n = ls[n][i];
cout << n << ' ';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Extra information in the output file |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Extra information in the output file |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Extra information in the output file |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
604 KB |
Extra information in the output file |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
0 ms |
348 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |