一直卡37

调了几天#3总是过不去

不想调了求助

#include<bits/stdc++.h>
#define int long long
using namespace std;
int Sum[1000001],n,k;
int deq[1000001],h,t;
int dp[1000001][2];
int f[300001][301];
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>Sum[i];
		Sum[i]+=Sum[i-1];
	}
	for(int ChainsawKiller=1;ChainsawKiller<=k;ChainsawKiller++)
	{
		memset(deq,0,sizeof(deq));
		deq[1]=0,h=t=1;
		for(int i=1;i<=n;i++)
		{
			while(h<t&&dp[deq[h]][0]-dp[deq[h+1]][0]<=(Sum[i]-Sum[deq[h+1]])*Sum[deq[h+1]]-(Sum[i]-Sum[deq[h]])*Sum[deq[h]])
				h++;
			dp[i][1]=dp[deq[h]][0]+(Sum[i]-Sum[deq[h]])*Sum[deq[h]];	
			f[i][ChainsawKiller]=deq[h];
			while(h<t&&((dp[i][0]-Sum[i]*Sum[i]-dp[deq[t]][0]+Sum[deq[t]]*Sum[deq[t]])*(Sum[deq[t-1]]-Sum[deq[t]])>(dp[deq[t]][0]-Sum[deq[t]]*Sum[deq[t]]-dp[deq[t-1]][0]+Sum[deq[t-1]]*Sum[deq[t-1]])*(Sum[i]-Sum[deq[t]])))
				t--;
			deq[++t]=i;
		}	
		for(int i=1;i<=n;i++)
			dp[i][0]=dp[i][1];
	}
	cout<<dp[n][1]<<endl;
	int p=n;
	for(int i=k;i>=1;i--)
	{
		cout<<f[p][i]<<" ";
		p=f[p][i];
	}
}
/*
199890017
299840021
*/