Array Division

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
/**
 * true if the given `arr` can be divided into `k` subarrays where the sum of
 * each subarray is at most `max_sum`
 */
bool is_possible(const vector<ll> &arr, const int k, ll max_sum) {
	// # of subarrays needed if sum of each subarray is at most max_sum
	int subarr_count = 0;
	// sum of the current subarray
	ll cur_sum = 0;
 
	for (const int &x : arr) {
		if (x > max_sum) { return false; }
 
		if (cur_sum + x > max_sum) {
			subarr_count++;
			cur_sum = 0;
		}
		cur_sum += x;
	}
	if (cur_sum > 0) { subarr_count++; }
 
	return subarr_count <= k;
}
 
int main() {
	int n, k;
	cin >> n >> k;
	vector<ll> arr(n);
	for (ll &i : arr) { cin >> i; }
 
	ll l = *max_element(begin(arr), end(arr));
	ll r = accumulate(begin(arr), end(arr), 0LL);
	while (l < r) {
		ll mid = (l + r) / 2;
		if (is_possible(arr, k, mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
 
	cout << l << endl;
}

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.LongStream;
 
public class ArrayDivision {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
 
		st = new StringTokenizer(br.readLine());
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) { arr[i] = Long.parseLong(st.nextToken()); }
		br.close();
 
		long l = Arrays.stream(arr).max().getAsLong();
		long r = Arrays.stream(arr).sum();
		while (l < r) {
			long mid = (l + r) / 2;
			if (is_possible(arr, k, mid)) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
 
		System.out.println(l);
	}
 
	/**
	 * true if the given `arr` can be divided into `k` subarrays where the sum
	 * of each subarray is at most `max_sum`
	 */
	private static boolean is_possible(long[] arr, int k, long max_sum) {
		// # of subarrays needed if sum of each subarray is at most max_sum
		int subarr_count = 0;
		// sum of the current subarray
		long cur_sum = 0;
		for (long x : arr) {
			if (x > max_sum) { return false; }
 
			if (cur_sum + x > max_sum) {
				subarr_count++;
				cur_sum = 0;
			}
			cur_sum += x;
		}
		if (cur_sum > 0) { subarr_count++; }
 
		return subarr_count <= k;
	}
}

n, k = map(int, input().split())
nums = list(map(int, input().split()))
 
 
def can_divide_arrays(max_sum: int) -> bool:
	"""
	Checks if it is possible to divide nums into k subarrays with each
	each subarray having a maximum sum of max_sum
 
	:param max_sum: The maximum sum of each subarray
	:return: If it is possible to divide nums with the above conditions.
	"""
	num_subarrays = 0
	cur_subarr_sum = 0
	for num in nums:
		if cur_subarr_sum + num <= max_sum:
			cur_subarr_sum += num
		elif num <= max_sum:
			num_subarrays += 1
			cur_subarr_sum = num
			if num_subarrays > k:
				return False
		else:
			return False
 
	# last sub seq is not counted in the loop
	num_subarrays += cur_subarr_sum > 0
 
	return num_subarrays <= k
 
 
left = max(nums)
right = sum(nums)
while left < right:
	mid = (left + right) // 2
	if can_divide_arrays(mid):
		right = mid
	else:
		left = mid + 1
 
print(left)