记录编号	320973	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]木棍分割	最终得分	100
用户昵称	GROWL GOOD BOYส็	是否通过	通过
代码语言	C++	运行时间	1.488 s
提交时间	2016-10-13 07:42:03	内存使用	1.26 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 50010
#define maxm 1010
using namespace std;
int n,m,ans1,l,r,f[maxn],a[maxn],sum[maxn],Mod=10007,t=0,g[maxn],k[maxn],ans2;
bool _check(int mid){
	//printf("mid=%d\n",mid);
	int sum=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>mid)return 0;
		if(sum+a[i]>mid){
			//printf("sum=%d a[%d]=%d\n",sum,i,a[i]); 
			cnt++;
			sum=0;
			if(cnt>m)return 0;
		}
		sum+=a[i];
	}
	return 1;
}
int main(){
	freopen("stick.in","r",stdin);freopen("stick.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]+=sum[i-1]+a[i];
	}
	l=1,r=sum[n];
	while(l<=r){
		int mid=(l+r)>>1;
		if(_check(mid))r=mid-1;
		else l=mid+1;
	}
	ans1=l;
	int pos=0;
	for(int i=1;i<=n;i++){
		while(sum[i]-sum[pos]>ans1) pos++;
		g[i]=pos;
	}
	
	k[0]=1; f[0]=1;m++;
	for(int i=1;i<=n;i++)k[i]=1;
	
	for(int i=1;i<=m;i++){;
		for(int j=1;j<=n;j++){
			if(!g[j]) f[j]=(k[j-1])%Mod;
			else f[j]=(k[j-1]-k[g[j]-1])%Mod;
			//printf("f[%d]=%d\n",j,f[j]);
		}
		k[0]=0;
		for(int j=1;j<=n;j++) k[j]=(k[j-1]+f[j]);
		ans2+=f[n];
		ans2%=Mod;
	}
	// f[t][i]=f[!t][ g[i] ]
	printf("%d %d\n",ans1,(ans2)%Mod);
	getchar();getchar();
	return 0;
}