记录编号	256762	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-05-01 20:44:33	内存使用	0.67 MiB

#include<cstdio>
using namespace std;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
const int maxn = 100000 + 10 ;
int n,k,s[maxn],l,r;
inline bool qs (int x){
	int num=0,ans=1;
	for(int i=1;i<=n;i++){
		if (s[i] > x) return false;
		if (s[i] + num <= x) num += s[i];
		else{
			num=s[i];
			ans++;
		}
	}
	if (ans<=k) return true;
	else return false;
}
int main(){
	freopen("expense.in","r",stdin);
	freopen("expense.out","w",stdout);
	read(n);read(k);
	for(int i=1;i<=n;i++){
		read(s[i]);
		r += s[i];
	}
	while (l < r-1){
		int m=(l+r)>>1;
		if (!qs(m)) l=m;
		else r=m;
	}
	if (qs(r)==true) printf("%d\n",r);
	else printf("%d\n",l);
	return 0;
}