Overview

This is a problem where we have a rope divided into segments of given lengths, and we cut it at segment boundaries to divide it into \(K\) pieces, minimizing the “length of the longest rope.” We binary search on the answer (the minimum of the maximum length) and greedily check whether a division is possible for a given upper limit.

Analysis

Key Insight

Consider the decision problem: “Can we make all rope pieces have length at most \(x\)?”

• If we can divide with upper limit \(x\), then we can always divide with any larger upper limit \(x' \ge x\) (the condition becomes more relaxed).
• Conversely, if it’s impossible with \(x\), it’s obviously impossible with any smaller upper limit.

In other words, the decision result has monotonicity with respect to \(x\) (it switches from false to true exactly once). Because of this property, we can use binary search to find the minimum \(x\) that gives “true.”

Why a Naive Approach Is Difficult

If we try all possible ways to cut (choosing \(K-1\) cut positions), there are \(\binom{N-1}{K-1}\) combinations, which is far too many for \(N \le 10^5\).

How to Build the Decision Function (Greedy)

Given an upper limit \(x\), we process segments from left to right:

• If adding the next segment to the current rope keeps it at most \(x\), add it.
• If it would exceed \(x\), cut here and start a new rope.

This is optimal (= minimizes the number of ropes needed). If the number of ropes produced by this greedy approach is at most \(K\), then “\(x\) is feasible” (since we can leave extra cuts unused, it’s possible to adjust to exactly \(K\) pieces).

Concrete Example

Let \(A=[2,3,4,2],\ K=2\), and check the upper limit \(x=6\):

• 2 + 3 = 5 (still OK)
• Adding the next 4 gives 9, which exceeds → cut (1st rope is 5)
• 2nd rope is 4 + 2 = 6

It fits in 2 ropes, so it’s feasible (true). On the other hand, with \(x=5\): 2+3=5, then cut, next is 4, adding 2 gives 6 which exceeds, so cut again — total of 3 ropes, which is infeasible (false).

Algorithm

1. Determine the search range
   • Lower bound \(lo = \max(A)\) (no matter how we cut, each segment must belong to some rope, so we can’t make the maximum shorter than the longest single segment)
   • Upper bound \(hi = \sum A\) (if we don’t cut at all, we have 1 rope of this length)
2. Build the decision function can(x)
   • Greedily pack from left, counting the number of ropes cnt
   • If cnt > K, return infeasible (false)
   • If we reach the end, return feasible (true)
3. Use the monotonicity of can(x) to binary search over \([lo, hi]\)
   • If can(mid) is true, set hi = mid
   • If false, set lo = mid + 1
4. The value of lo when the search ends is the answer

Complexity

• Time complexity: \(O(N \log(\sum A))\) (The decision function is \(O(N)\), and binary search runs \(\log(\sum A)\) times)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Initialize the binary search with lo = max(A), hi = sum(A) (this ensures the range narrows correctly).

• In the greedy decision, strictly follow the rule “cut when it exceeds,” and return early when cnt > K for efficiency.

• An important point is that it suffices to make at most \(K\) pieces (since not making extra cuts won’t increase the count, if cnt <= K we can adjust to exactly \(K\) pieces).

  Source Code

import sys

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

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

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

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

    print(lo)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.