Overview

Given logs, cut them at \(K\) places and minimize the maximum length \(M\) of the resulting fragments.

Approach

In this problem, when dividing logs into several fragments, we need to cut them so that “the longest fragment is as short as possible.” A naive approach would be to try all possible combinations of cuts, but since \(N\) can be up to \(2 \times 10^5\), the number of combinations is extremely large, making this impractical (it would result in TLE due to computational complexity).

The key observation is that the optimization problem of “finding the minimum value of the maximum fragment length \(M\)” can be efficiently solved using binary search. In other words, by repeatedly solving the decision problem “Is it possible to divide the logs such that the maximum fragment length is at most some value \(x\)?”, we can find the minimum \(M\).

The decision problem itself can be solved greedily. We process pieces from left to right, accumulating them, and whenever adding the next piece would exceed the upper limit \(x\), we make a cut at that point. If the number of cuts is at most \(K\), the answer is OK; otherwise, it’s NG.

This is a problem where the classic technique of “finding the value to minimize via binary search, with greedy evaluation for the feasibility check” can be applied.

Algorithm

1. Set the binary search range

   • Minimum: the longest single piece (no fragment can be shorter than this)
   • Maximum: the sum of all pieces (everything connected together)

2. Perform binary search

   • Use mid as the “upper limit on maximum fragment length” and check whether it’s possible to divide within that constraint
   • The decision function is_possible(max_len) greedily forms fragments and checks whether the required number of cuts is at most \(K\)

3. Greedy division check

   • Group pieces from left to right as if taking a cumulative sum
   • When the sum is about to exceed max_len, make a cut there
   • If the number of cuts is at most \(K\), it’s OK

4. Output the final answer

Complexity

• Time complexity: \(O(N \log(\text{sum}(A)))\)
  • The binary search range is at most around \(10^{14}\), so \(\log\) is at most about 50
  • The decision function traverses the array once in \(O(N)\)
• Space complexity: \(O(N)\)
  • \(O(N)\) for storing the input array

Implementation Notes

• Set the binary search range correctly (left = max(A), right = sum(A))

• Count the number of cuts accurately (the first fragment does not require a cut)

• For fast input reading, using sys.stdin.read or similar is recommended

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 二分探索で答えを求める
    def is_possible(max_len):
        # 各断片の長さがmax_len以下になるように切る
        cuts = 0
        current_sum = 0
        for a in A:
            if current_sum + a > max_len:
                cuts += 1
                current_sum = a
                if cuts > K:
                    return False
            else:
                current_sum += a
        return True

    left = max(A)
    right = sum(A)
    while left < right:
        mid = (left + right) // 2
        if is_possible(mid):
            right = mid
        else:
            left = mid + 1
    print(left)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.