The Great Assignment Split Crisis
Time: 1 s
Memory: 125 MB
Memory: 125 MB
At Jatiya Kabi Kazi Nazrul Islam University, a group of Computer Science students received a large assignment consisting of n pages. Each page has an associated difficulty value. The assignment needs to be divided among k students.
To ensure fairness, the assignment must be split into k continuous segments, with each student receiving exactly one segment.
The difficulty of a segment is defined as the sum of the difficulties of its pages.
The students want to divide the assignment in such a way that the maximum difficulty assigned to any student is as small as possible.
Your task:
Determine a way to partition the n pages into k continuous segments such that the maximum segment difficulty is minimized.
To ensure fairness, the assignment must be split into k continuous segments, with each student receiving exactly one segment.
The difficulty of a segment is defined as the sum of the difficulties of its pages.
The students want to divide the assignment in such a way that the maximum difficulty assigned to any student is as small as possible.
Your task:
Determine a way to partition the n pages into k continuous segments such that the maximum segment difficulty is minimized.
Input
The first line contains two integers n and k — the number of pages in the assignment and the number of students.The second line contains n positive integers [ \(x_1,x_2,\ldots,x_n\) ]: the difficulty of each page.
Constraint
\(1 \le n \le 2 \cdot 10^5\)\(1 \le k \le n\)
\(1 \le x_i \le 10^9\)
Output
Print one integer — the minimum possible maximum difficulty any student gets in the optimal division.
Examples
| Input | Output |
|---|---|
|
5 3
2 4 7 3 5 |
8
|
Notes
Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.
Problem Info
| Problem ID | 798 |
| Time Limit | 1000 ms |
| Memory Limit | 128000 KB |
| Moderators | Nabeel_Ahsan , tamjid_hossen , shazidmashrafi |
Statistics
Submit
You need to Login or Registration for submit your solution