1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<stdio.h>
int a[100200];
int n,m;
bool judge(int x) {
	int sum=0,cnt=1;
	for(int i=0; i<n; i++) {
		if(a[i]>x)
			return false;
		sum+=a[i];
		if(sum>x) {
			cnt++;
			sum=a[i];
		}
	}
	if(cnt>m)
		return false;
	else
		return true;
}
int main() {
	while(scanf("%d %d",&n,&m)!=EOF) {
		int l=0,r=0;
		for(int i=0; i<n; i++) {
			scanf("%d",&a[i]);
			r+=a[i];
		}
		int mid,res;
		while(r>=l) {
			mid=(l+r)/2;
			if(judge(mid)) {
				res=mid;
				r=mid-1;
			} else
				l=mid+1;
		}
		printf("%d\n",res);
	}
	return 0;
}