#include<bits/stdc++.h>
using namespace std;
vector<long long>pref, v;
int n, k;
long long cost(int i, int j){
long long L = pref[j] - pref[i - 1], R = pref[n] - pref[j];
return L * R;
}
long long rec(int l, int k){
long long res = 0;
if(l > n)return -1e18;
if(l == n || k == 0)return 0;
for(int i = l;i <= n;++i){
res = max(res, cost(l, i) + rec(i + 1, k - 1));
}
return res;
}
int main()
{
cin >> n >> k;
pref.resize(n + 1);
v.resize(n + 1);
for(int i = 1;i <= n;++i){
cin >> v[i];
pref[i] = pref[i - 1] + v[i];
}
vector<vector<long long>>dp(k + 1, vector<long long>(n + 1, -1e18));
vector<vector<pair<int, int>>>par(k + 1, vector<pair<int, int>>(n + 1, {-1, -1}));
for(int i = 1;i <= n;++i)dp[0][i] = 0;
for(int i = 1;i <= k;++i)dp[k][n] = 0;
for(int K = 1;K <= k;++K){
for(int i = n;i >= 1;--i){
for(int j = i;j < n;++j){
long long num = cost(i, j) + dp[K - 1][j + 1];
if(dp[K][i] < num){
dp[K][i] = num;
par[K][i] = {K - 1, j + 1};
}
// cout << "dp[" << K << "][" << i << "]=" << dp[K][i] << ": {" << par[K][i].first << ", " << par[K][i].second << "}\n";
}
}
}
long long mx = -1e18;
pair<int, int>num;
for(int i = 1;i <= n;++i){
if(mx < dp[k][i]){
mx = dp[k][i];
num = {k, i};
}
}
vector<int>ans;
while(num.first > 0){
ans.push_back(num.second);
num = par[num.first][num.second];
}
cout << mx << '\n';
for(int i : ans)cout << i << " ";
// cout << mx << '\n' << rec(1, k);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
declared answer doesn't correspond to the split scheme: declared = 108, real = 99 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
300 KB |
declared answer doesn't correspond to the split scheme: declared = 1093956, real = 754058 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
declared answer doesn't correspond to the split scheme: declared = 610590000, real = 507121050 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
300 KB |
declared answer doesn't correspond to the split scheme: declared = 21503404, real = 14766072 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
697 ms |
1152 KB |
declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1569368052 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2069 ms |
8892 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |