#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
const int inf = 1e9 + 9;
const int mxn = 1e5 + 2;
const int mod = 1e9 + 7;
int dp[mxn][201] , a[mxn];
int pre[mxn];
int id[mxn][201];
int sq(int x) {
return x * x;
}
signed main() {
int n , k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i-1] + a[i];
}
for (int i = 0; i <= k; i++) dp[0][i] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = sq(pre[i]);
for (int j = 1; j < i; j++) {
dp[i][j] = inf;
for (int q = 0; q < i; q++) {
if (dp[i][j] > dp[q][j-1] + sq(pre[i] - pre[q])) {
dp[i][j] = dp[q][j-1] + sq(pre[i] - pre[q]);
id[i][j] = q;
}
}
}
}
cout << (sq(pre[n]) - dp[n][k]) / 2 << '\n';
int x = id[n][k];
while (k > 0) {
if (x == 0) break;
cout << x << ' ';
k--;
x = id[x][k];
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Incorrect |
1 ms |
4444 KB |
Unexpected end of file - int32 expected |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Incorrect |
1 ms |
4444 KB |
Unexpected end of file - int32 expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6748 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Incorrect |
4 ms |
6744 KB |
Unexpected end of file - int32 expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
425 ms |
8804 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Incorrect |
384 ms |
8560 KB |
Unexpected end of file - int32 expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2028 ms |
11100 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2057 ms |
10852 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |