This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int szn = 10001,szk=201;
int dp[szn][szk],arr[szn],pre[szn],n,k;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 0;i<n;i++) {
cin >> arr[i];
pre[i] = arr[i];
if (i) pre[i] += pre[i-1];
}
memset(dp,0,sizeof(dp));
for (int c = 1;c<=k;c++){
for (int i = c;i<n;i++){
for (int j = 0;j<i;j++){
dp[i][c] = max(dp[i][c],dp[j][c-1]+(pre[j]*(pre[i]-pre[j])));
}
}
}
cout << dp[n-1][k] << '\n';
int t = n-1, c = k;
vector<int> ans;
for (int i = n-2;~i;i--){
if (dp[t][c] == dp[i][c-1]+pre[i]*(pre[t]-pre[i])){
ans.push_back(i+1);
t = i;
c--;
}
if (!c) break;
}
for (int i = ans.size()-1;~i;i--) cout << ans[i] << ' ';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |