#include <bits/stdc++.h>
using namespace std;
long long n,k;
long long s[100005];
long long dp[100005][201];
int last[100005][201];
void solve(int nr, int st, int dr, int stOpt, int drOpt)
{
if(st > dr)
return;
int mij=(st+dr)/2;
long long maxi=0, best=-1;
for(int j=stOpt;j<=min(drOpt, mij);j++)
{
long long nval= (s[mij]-s[j-1])*s[j-1] + dp[j-1][nr-1];
if(nval > maxi)
{
maxi=nval;
best=j;
}
}
dp[mij][nr]=maxi;
last[mij][nr]=best;
solve(nr, st, mij-1, stOpt, best);
solve(nr, mij+1, dr, best, drOpt);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
s[i]+=s[i-1];
for(int nr=1;nr<=k;nr++)
solve(nr, 0, n, 0, n);
cout<<dp[n][k]<<'\n';
int nr=k;
int p=n;
vector<int> ans;
while(true)
{
p = last[p][nr];
nr--;
if(!p)
break;
ans.push_back(p);
}
reverse(ans.begin(), ans.end());
for(int it : ans)
cout<<it<<' ';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
declared answer doesn't correspond to the split scheme: declared = 108, real = 92 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Integer 50 violates the range [1, 49] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
716 KB |
Integer 200 violates the range [1, 199] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2636 KB |
declared answer doesn't correspond to the split scheme: declared = 21503404, real = 21503392 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
24012 KB |
declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1496550000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
74 ms |
131076 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |