Minimum maximum - MarisaOJ: Marisa Online Judge

Minimum maximum

Time limit: 1000 ms
Memory limit: 256 MB
Given an array $A$ with $n$ elements, find the smallest integer $x$ such that the array $A$ can be divided into exactly $k$ contiguous subarrays, each with a sum not exceeding $x$. ### Input - The first line contains two integers $n, k$. - The second line contains $n$ integers $A_i$. ### Output - Print an integer $x$ as the answer. ### Constraints - $1 \le k \le n \le 10^5$. - $1 \le A_i \le 10^9$. ### Sample Input: ``` 5 2 5 4 3 2 1 ``` Output: ``` 9 ``` **Note: A possible division `[5 4] [3 2 1]`. There is no way to divide $A$ if $x$ is smaller than $9$**