记录编号	435572	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-08-09 21:06:53	内存使用	0.67 MiB

#include <stdio.h>
int n,m,a[100005],len,l=0,r=1000000000;;
bool check(int w){
	 int sum=0,tot=1;
	 for(int i=1;i<=n;i++){ 
	     if(a[i]>=w) return false;
	     if(a[i]+sum<w) sum+=a[i];
	     else sum=a[i],tot++;
	 }
     if(tot<=m) return true;
     else return false;
}
int main(){
	freopen("expense.in","r",stdin);
	freopen("expense.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	while(l<r){
		  int mid=(l+r)>>1;
		  if(check(mid)) r=mid;
		  else l=mid+1,len=mid;
	}printf("%d",len);
}