QUESTION

The hero of this story is a toddler named BooBoo. Inspired by the legendary competitive coder Gena, BooBoo has also started preparing to race to the top of the ranks.\n\nBooBoo is going to practice N different problems in the exact given order over the next M days. For each problem, he writes down the amount of time qi he will take to think and code the ith problem (He is quite good at estimating!). Before starting on the problems, he took advice from experienced competitive programmers on his practice routine and almost all of them advised him to keep his daily load at the minimum possible and avoid over training.\n\nSince BooBoo already has N problems to solve, he asks you to find the minimum time T such that training everyday for a time ti<=T is sufficient to solve all the N problems in M days.\n\nNote : Unlike in real world, you cannot think on a problem on one day and solve it on the other day. You need to do it on the very same day!\nInput Format:\nThe first line contains two space-separated integers N and M. The next line contains N space separated integers denoting the time qi required to solve the ith problem.\nOutput Format:\nThe output consists of one integer, the minimum time T as described in the problem statement.\nSAMPLE INPUT \n5 3\n1 2 2 1 3\n\nSAMPLE OUTPUT \n3\n\nExplanation\nBy setting T = 3, we can solve 1st two questions on day 1, next two on day 2 and 5th one on day 3.

“TESTCASE_1”: “5 3\n1 2 2 1 3\n###—###SEPERATOR—###—\n3”, “TESTCASE_2”: “10 2\n5 8 2 9 20 54 1 7 4 5\n###—###SEPERATOR—###—\n71”, “TESTCASE_3”: “7 4\n7 3 1 9 3 6 5\n###—###SEPERATOR—###—\n10”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<bits/stdc++.h>
using namespace std;
const int N = 100031;
int n, m;
long long t[N];
long long sum[N];
int check(long long thold)
{
	int done = 0;
	int res = 0;
	while (done < n)
	{
		int cur = done;
		while (cur + 1 <= n&&sum[cur + 1] - sum[done] <= thold)
			++cur;
		if (cur == done)
			return 1e9;
		res++;
		done = cur;
	}
	return res;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> t[i];
	}
	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + t[i];
	}
	long long l, r;
	
	l = 1;
	r = 1e17;
	
	while (l < r)
	{
		long long mid = l + r;
		mid /= 2;
		if (check(mid) <= m)
			r = mid;
		else
			l = mid + 1;
	}
	cout << l << endl;
	return 0;
}