#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 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++) {
dp[i][j] = min(dp[i][j] , dp[q][j-1] + sq(pre[i] - pre[q]));
}
}
}
cout << (sq(pre[n]) - dp[n][k]) / 2 << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2808 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2396 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
451 ms |
4528 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2054 ms |
4360 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2008 ms |
4700 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |