题目描述

你正在玩一个关于长度为

k+1

次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）。

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。

你想要最大化最后的总得分。

输入格式

第一行包含两个整数

个非负整数

(0≤ai​≤104)，表示前文所述的序列。

输出格式

第一行输出你能获得的最大总得分。

第二行输出

个介于

之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。

第

个整数

之间把块分开。

如果有多种方案使得总得分最大，输出任意一种方案即可。

输入输出样例

输入

3

输出

5

说明/提示

你可以通过下面这些操作获得

108

4×(1+3+4+0+2+3)=52

个元素后面分开，获得

(1+3)×(4+0+2+3)=36

个元素后面分开，获得

分。

所以，经过这些操作后你可以获得四块

并获得

分。

【限制与约定】

第一个子任务共

分，满足

2≤n≤1000,1≤k≤min{n−1,200}。

第五个子任务共

分，满足

2≤n≤10000,1≤k≤min{n−1,200}。

第六个子任务共

分，满足

2≤n≤100000,1≤k≤min{n−1,200}。

感谢

@larryzhong

提供的加强数据。

代码实现：

#include<bits/stdc++.h>
using
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return
((s[x]*s[x]-dp[l&1^1][x])-(s[y]*s[y]-dp[l&1^1][y]))/(1.0*(s[x]-s[y]));
int
i=1;i<=n;i++)
for(reg
i=1;i<=k;i++){
h=0,t=0;
j=1;j<=n;j++){
while(h<t&&slp(q[h],q[h+1],i)<=s[j])h++;
tmp=q[h];
dp[i&1][j]=dp[i&1^1][q[h]]+s[q[h]]*(s[j]-s[q[h]]);
p[i][j]=q[h];
while(h<t&&slp(q[t],j,i)<=slp(q[t-1],q[t],i))t--;
printf("%lld\n",dp[k&1][n]);
x=n;