#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define m first
#define n second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=2e5+3;
ll dp[202][N],opt[202][N],pf[N],ans=0;
int n,k,a[N];
vector<int> track;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
For(i,1,n) {
cin >> a[i];
pf[i]=pf[i-1]+a[i];
}
pair<int,int> cur={0,0};
For(j,1,k) {
For(i,j,n-1) {
For(p,j-1,i-1) {
if (dp[j-1][p]+(pf[i]-pf[p])*(pf[n]-pf[i])>dp[j][i]) {
opt[j][i]=p;
}
dp[j][i]=max(dp[j][i],dp[j-1][p]+(pf[i]-pf[p])*(pf[n]-pf[i]));
}
}
For(i,1,n-1)
if (dp[j][i]>ans) {
ans=dp[j][i];
cur={j,i};
}
}
cout << ans << endl;
while(cur.m>0) {
track.pb(cur.n);
cur={cur.m-1,opt[cur.m][cur.n]};
}
reverse(all(track));
for(auto el: track) cout << el << " ";
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... |