记录编号	320741	评测结果	AAAAAAAAAA
题目名称	305.[HAOI 2008]木棍分割	最终得分	100
用户昵称	GROWL GOOD BOYส็	是否通过	通过
代码语言	C++	运行时间	1.344 s
提交时间	2016-10-12 17:54:20	内存使用	1.27 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=50010,mod=10007;
int N,M;
int A[maxn];
int  f[maxn],g[maxn],k[maxn],sum[maxn];
int Ans1,Ans2=0;

bool pan(int x)
{
         for(int i=1;i<=N;i++)if(A[i]>x)return 0;
        int ci=0;
		int la=0;
		for(int i=1;i<=N;i++)
		{
		   if(sum[i]-sum[la]>x)
		   {
              ci++;
              la=i-1;
           }
		}
		if(la!=N)ci++;
        return ci<=M;
        
}

int main()
{
	freopen("stick.in","r",stdin);
	freopen("stick.out","w",stdout);
	scanf("%d%d",&N,&M);
	M++;
	int l=1,r=0;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&A[i]);r+=A[i];sum[i]=sum[i-1]+A[i];
	}
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(pan(mid))Ans1=mid,r=mid;
		else l=mid+1;
	}
	if(pan(l))Ans1=l;
	Ans2=0;
	int pos=0;
    for(int i=1;i<=N;i++)
	{
            while(sum[i]-sum[pos]>Ans1)pos++;
            g[i]=pos;
    }
	for(int i=1;i<=N;i++)f[i]=0,k[i]=1;f[0]=1,k[0]=1;
	for(int i=1;i<=M;i++)
	{
            for(int j=1;j<=N;j++)
            {
              f[j]=(k[j-1]-k[g[j]-1])%mod;
            }
            k[0]=0;
            for(int j=1;j<=N;j++)k[j]=k[j-1]+f[j];
            Ans2=(Ans2+f[N])%mod;
    }
	printf("%d %d",Ans1,Ans2);
	fclose(stdin);
	fclose(stdout);
	return 0;
}