比赛 皇后 评测结果 AAAAAAAAAA
题目名称 划分数列 最终得分 100
用户昵称 Emine 运行时间 0.034 s
代码语言 C++ 内存使用 1.06 MiB
提交时间 2017-03-19 19:47:00
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=101000;
int n,k,s[maxn],c[maxn],maxa;

int read()
{
	int x=0;
	char ch=getchar();
	while(ch<='9'&& ch>='0')
	{
		x=x*10+ch-48;
		ch=getchar();
    }
	return x;
}

bool cha(int len)
{
	int sum=0,cn=1;
	for(int i=1;i<=n;i++)
	{
		sum+=c[i];
		if(sum>len)
		  cn++,sum=c[i];
	}
	return cn<=k;
}
 
int find()
{
	int l=maxa,r=s[n],mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(cha(mid)) 
		  r=mid-1;
		else 
		  l=mid+1;
	}
	return l;
}
int main()
{
	freopen("seqa.in","r",stdin);
	freopen("seqa.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++)
	{
		c[i]=read();
		s[i]=s[i-1]+c[i];
		maxa=max(maxa,c[i]);
	}
	printf("%d\n",find());
	return 0;
}