C++11(clang++ 3.9) 解法, 执行用时: 664ms, 内存消耗: 1764K, 提交时间: 2020-03-27 18:03:47

#include<cstdio>
#include<algorithm>
#define N 50010
#define mod 10007
using namespace std;
int n,m,a[N],sl[N],f[2][N],sum[2][N];
bool judge(int mid)
{
	int i=0,now=0,cnt=0;
	for(i=1;i<=n;i++)
	{
		if(now+a[i]>mid) now=0,cnt++;
		now+=a[i];
	}
	return cnt<=m;
}
int main()
{
	int i,j,l=0,r=0,mid,ans=-1,p=0,ret=0,d;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%d",&a[i]),l=max(l,a[i]),r+=a[i],sl[i]=sl[i-1]+a[i];
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(judge(mid)) ans=mid,r=mid-1;
		else l=mid+1; 
	}
	printf("%d ",ans);
	for(i=0;i<=n;i++)
	sum[0][i]=1;
	for(i=d=1;i<=m+1;i++,d^=1)
	{
		sum[d][0]=p=0;
		for(j=1;j<=n;j++)
		{
			while(sl[j]-sl[p]>ans) p++;
			f[d][j]=sum[d^1][j-1];
			if(p) f[d][j]=(f[d][j]-sum[d^1][p-1]+mod)%mod;
			sum[d][j]=(sum[d][j-1]+f[d][j])%mod;
		}
		ret=(ret+f[d][n])%mod;
	}
	printf("%d\n",ret);
	return 0;
}