#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 = LLONG_MAX / 2;
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 = 0; i < mxn; i++)
for(int j = 0; j < mxk; j++) {
dp[i][j] = gay;
if(j == 0) {
dp[i][j] = p[i] * p[i];
ls[i][j] = i;
}
}
dp[1][0] = a[1] * a[1];
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] != -1; 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--) {
// cout << n << ' ' << i << endl;
if(n == 0) return i;
v.push_back(n);
n = ls[n][i];
}
while(v.size() > 1) {
cout << v.back() << ' ';
v.pop_back();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Runtime error |
1 ms |
600 KB |
Execution failed because the return code was nonzero |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Runtime error |
5 ms |
604 KB |
Execution failed because the return code was nonzero |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
600 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
3 ms |
600 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Runtime error |
113 ms |
1048 KB |
Execution killed with signal 11 |
4 |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
0 ms |
512 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |