记录编号	257537	评测结果	AAAAAAAAAA
题目名称	167.[USACO Mar07] 月度花费	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2016-05-02 13:17:33	内存使用	0.70 MiB

#include <cstring>
#include <cstdio>
#include <iostream>
#define maxn 100010
int read(){
	int x=0, f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x =x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
using namespace std;
int N , M ;
int c[maxn];
int l, r;

bool check(int x){
	int cnt=0, num =0;
	for(int i=1; i<=M ; i++){
		while(c[cnt+1]+num <=x){
			num += c[cnt+1];
			++cnt;
			if(cnt>=N )return 1;
		}
		num =0;
	}
	if(cnt<N )return 0;
}
int main(){
	freopen("expense.in","r",stdin);
	freopen("expense.out","w",stdout);
	N =read(), M =read();
	for(int i=1; i<=N ; i++){
		c[i] =read();
		l =max(l, c[i]);
		r +=c[i];
	}
	int ans, mid;
	while(l<=r){
		mid =(l+r)>>1;
		if(check(mid))ans=mid, r=mid-1;
		else l=mid+1;
	}	
	printf("%d", ans);
	return 0;
}