记录编号	44690	评测结果	AAAAAAAAAA
题目名称	划分数列	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2012-10-19 18:24:44	内存使用	3.91 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int a[100010],s[100010];

int main(void)
{
	freopen("seqa.in","r",stdin);
	freopen("seqa.out","w",stdout);
	int i,n,k,l,r,mid,c,last;
	bool ok;
	cin>>n>>k;
	for (i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	l=0;
	r=s[n];
	mid=r>>1;
	while (l<r)
	{
		ok=true;
		last=0;
		c=0;
		for (i=1;i<=n;i++)
		{
			if (s[i]-s[last]>mid)
			{
				i--;
				c++;
				if (c>=k)
				{
					ok=false;
					break;
				}
				last=i;
			}
		}
		if (ok)
		{
			r=mid;
			mid=(l+r)>>1;
		}
		else
		{
			l=mid+1;
			mid=(l+r)>>1;
		}
	}
	cout<<mid<<endl;
	return(0);
}