Overview

Given a sequence of loads \(A_1,\dots,A_N\), we want to divide them into \(K\) contiguous segments while maintaining their original order, maximizing the minimum segment sum.

Analysis

Key Observations

• Since the loads assigned to each truck must be contiguous, this is essentially a problem of dividing an array into \(K\) contiguous segments.
• The goal is to maximize the “minimum segment sum,” but directly searching for the “optimal partition” involves \(K-1\) partition points, leading to a massive number of combinations (brute-force search is infeasible).

Converting to a Decision Problem

Instead of directly finding the “maximum of the minimum segment sum,” consider the following decision problem:

For a given value \(x\), can the array be divided into \(K\) contiguous segments such that every segment sum is at least \(x\)?

If this is possible, then “the minimum segment sum can be made at least \(x\)” = “the answer is at least \(x\).”

Why a Greedy Approach Works for the Decision Problem

Since \(A_i \ge 1\) (positive values), the optimal strategy is to accumulate sums from left to right and cut a segment as soon as the sum reaches \(x\) or more.

• Cutting as early as possible leaves more elements for the remaining segments, thereby maximizing the number of segments we can create.
• Therefore, using this greedy method, we count “how many segments with sum at least \(x\) can be created,” and if we can create \(K\) or more, it is feasible.

Concrete Example

For \(A=[2,1,3,2,2],\ K=3,\ x=4\):
Greedily accumulating from the left: - \(2+1+3=6 \ge 4\) → 1st segment - Next, \(2+2=4 \ge 4\) → 2nd segment - No elements remain, so only 2 segments can be formed, not \(3\) → infeasible

Algorithm

1. Binary Search (Searching for the Answer)

Binary search for the answer (the minimum segment sum we want to maximize) over the range \(0\) to \(\sum A_i\).

• Try a value \(mid\); if feasible(mid) described below returns True, “we might be able to go larger,” so set lo = mid
• If False, “it’s too large,” so set hi = mid - 1

2. Decision Function feasible(x) (Greedy)

Accumulate a running sum s from left to right. Whenever s >= x, cut a segment, increment the segment count cnt, and reset s = 0.
Return True as soon as cnt >= K (we successfully created \(K\) segments).

This method is correct because, for a sequence of positive numbers, the “cut as soon as the threshold is reached” strategy maximizes the number of segments, which is sufficient for the feasibility check.

Complexity

• Time complexity: \(O(N \log(\sum A_i))\)
  (Binary search runs approximately \(\log(\sum A_i)\) iterations, each scanning the array once in \(O(N)\))
• Space complexity: \(O(1)\) (only constants beyond the input array)

Implementation Notes

• To prevent infinite loops in binary search, use ceiling division for the midpoint: mid = (lo + hi + 1) // 2 (this is the standard technique when updating lo).

• In feasible, returning True immediately when cnt >= K provides a slight speedup.

• The upper bound hi is at most \(\sum A_i\) (the sum when all loads are placed on a single truck), which is sufficient.

  Source Code

import sys

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

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

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

    print(lo)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.