bzoj4590: [Shoi2015]自动刷题机 二分

#include<cstdio>
#include<algorithm>
using std::max;
typedef long long ll;
ll l,r,s,m;
int n,k,t,a[100000];
int foo(ll v){
	for(int i=t=s=0;
	i!=n;++i)
		if((s=max(
		s+a[i],0ll))>=v)
			s=0,++t;
	return t;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i!=n;++i)
		scanf("%d",a+i);
	l=1,r=1e14;
	while(l!=r)
		foo(m=l+r>>1)
		>k?l=m+1:r=m;
	if(foo(l)!=k){
		puts("-1");
		return 0;
	}
	printf("%lld ",l);
	l=1,r=1e14;
	while(l!=r)
		foo(m=l+r+1>>1)
		<k?r=m-1:l=m;
	printf("%lld\n",l);
}