Overview

Given an array \(A_1,\ldots,A_N\), we want to split it into \(K+1\) contiguous pieces while preserving order, minimizing the maximum piece sum \(M\). We binary search on the answer \(M\) and greedily check whether a split is feasible for a given upper bound \(x\).

Analysis

Key Observation

Consider the decision problem: “Can we make the maximum piece sum at most \(x\)?”

• If \(x\) is large enough, the split is possible.
• If \(x\) is too small, it is impossible.
• In other words, “possible/impossible” is monotonic with respect to \(x\) (the larger \(x\) is, the easier it is to achieve).

Because of this monotonicity, we can binary search for the minimum \(x\) (= the answer).

Why a Brute-Force Approach Is Infeasible

There are \(N-1\) possible cut positions, and we need to choose \(K\) of them, giving \(\binom{N-1}{K}\) combinations. For \(N \le 2\times 10^5\), exhaustive search is completely infeasible.

How to Build the Feasibility Check (Greedy)

When we want to keep the maximum piece sum at most \(x\), we process from left to right:

• If adding the current element to the current piece does not exceed \(x\), add it.
• If it would exceed \(x\), cut here and start a new piece.

This greedy approach minimizes the number of pieces. If the resulting number of pieces is at most \(K+1\), then splitting with upper bound \(x\) is feasible.

Note: The problem asks for “exactly \(K\) cuts to make \(K+1\) pieces,” but having fewer pieces (\(\le K+1\)) is also fine. Since all values are positive, we can always further subdivide a piece without increasing the maximum piece sum (it won’t get worse), so we can adjust to exactly \(K+1\) pieces in the end.

Concrete example: \(A=[3,1,4,1,5],\ K=2\) (3 pieces), checking \(x=5\) Greedily packing: - \(3+1=4\) (still OK), adding the next \(4\) gives \(8\) which exceeds \(5\) → cut here (piece sum 4) - Next: \(4+1=5\) (OK), adding the next \(5\) gives \(10\) which exceeds \(5\) → cut here (piece sum 5) - Last piece: \(5\) (piece sum 5)

The number of pieces is 3, which is \(\le K+1=3\), so it is feasible.

Algorithm

1. Determine the search range for the answer \(M\)
   • Lower bound \(lo = \max(A_i)\) (no matter how we split, the maximum piece sum is at least the largest element)
   • Upper bound \(hi = \sum A_i\) (if we don’t cut at all, this is the total length)
2. Binary search on \(x\)
   • feasible(x): Can we achieve a maximum piece sum of at most \(x\) with at most \(K+1\) pieces?
3. If feasible(mid) is true, decrease the upper bound; if false, increase the lower bound.
4. When \(lo=hi\), that value is the minimum achievable maximum piece sum (the answer).

Feasibility check feasible(x) (greedy): - Number of pieces cnt=1, current piece sum s=0 - Process from left to right: if s+a <= x, then s+=a - Otherwise, start a new piece: cnt += 1, s = a - If at any point cnt > K+1, return impossible (False) - If we reach the end, return possible (True)

Complexity

• Time complexity: \(O(N \log(\sum A_i))\) (The binary search runs \(\log(\sum A_i)\) times, and each feasibility check takes \(O(N)\))
• Space complexity: \(O(N)\) (To store the array \(A\))

Implementation Notes

• The lower bound of the binary search must be max(A) (any \(x\) smaller than this is definitely impossible).

• The key trick in the feasibility check is to accept “number of pieces \(\le K+1\)” (it doesn’t have to be exactly \(K+1\), for the reason explained in the analysis).

• \(\sum A_i\) can be as large as \(2\times 10^5 \times 10^9 = 2\times 10^{14}\), so 64-bit integers are required in languages other than Python.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    need_segments = K + 1

    lo = max(A)
    hi = sum(A)

    def feasible(x: int) -> bool:
        cnt = 1
        s = 0
        for a in A:
            if s + a <= x:
                s += a
            else:
                cnt += 1
                s = a
                if cnt > need_segments:
                    return False
        return True

    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1

    print(lo)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.