Overview

This problem asks: given a row of packages, divide them into groups (carts) without changing their order, such that the total weight of each group is equal, and find the maximum number of groups possible.

Analysis

1. Using Prefix Sums

When dividing packages into consecutive groups, let the total weight of each group be \(w\). Then, the “cumulative weight of packages (prefix sum)” at each group boundary, counted from the left, must take the values \(w, 2w, 3w, \dots, kw\) (where \(kw\) is the total weight \(S\) of all packages).

For example, if the weights are \([1, 2, 1, 1, 1]\) and we decide each group’s weight should be \(w=3\): - The prefix sums are \([1, 3, 4, 5, 6]\). - The prefix sums at the boundaries are \(3, 6\), both of which exist in the prefix sum list.

2. Candidates for Each Group’s Weight \(w\)

To maximize the number of carts \(k\), we need to make each group’s weight \(w\) as small as possible. The possible values of \(w\) are limited to “the total weight when combining the first few packages from the left”. In other words, the \(N\) values contained in the prefix sum list are the candidates for \(w\).

3. Efficient Verification

To check whether a given \(w\) satisfies the conditions, we verify the following two points: 1. The total weight \(S\) is divisible by \(w\) (\(k = S/w\) is an integer). 2. The values \(2w, 3w, \dots, (k-1)w\) all exist in the prefix sum list.

By storing the prefix sum list in a set, we can check whether a specific value exists in \(O(1)\) time.

Algorithm

1. Compute the prefix sums of the package weights and store them in a list prefix_sum and a set p_set.
2. Let \(S\) be the total weight of all packages.
3. Examine each element \(w\) of prefix_sum in increasing order (from left to right), and perform the following:
   • If \(S\) is not divisible by \(w\), skip to the next \(w\).
   • If \(S\) is divisible by \(w\), let \(k = S/w\).
   • For \(j = 2, 3, \dots, k-1\), check whether \(j \times w\) is contained in p_set.
   • If all values are contained, then \(k\) is the maximum number of groups, so output it and terminate.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Computing the prefix sums and storing them in the set takes \(O(N)\).
  • The number of checks in the loop, even in the worst case (e.g., when all package weights are \(1\)), is \(O(N/1 + N/2 + \dots + N/N) = O(N \log N)\) by the harmonic series property, which is sufficiently fast.
• Space Complexity: \(O(N)\)
  • The list and set for storing prefix sums use \(O(N)\) memory.

Implementation Notes

• Try from the smallest \(w\): Since prefix_sum is always in ascending order, by trying from the beginning of the list, the first \(w\) that satisfies the conditions gives the largest number of groups \(k\).

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), using sys.stdin.read().split() or similar to read all input at once can reduce execution time.

• Early Termination: By terminating the computation and outputting the result as soon as a valid \(w\) is found, unnecessary exploration is avoided.

  Source Code

import sys

# 競技プログラミングにおける標準的な高速入力処理
def solve():
    # 全ての入力を一度に読み込み、スペース区切りでリスト化する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 荷物の個数 N
    n = int(input_data[0])
    # 各荷物の重さ Hi
    h = list(map(int, input_data[1:]))
    
    # 累積和を計算する
    # prefix_sum[i] は左から i+1 番目までの荷物の総重量を表す
    prefix_sum = [0] * n
    current_sum = 0
    for i in range(n):
        current_sum += h[i]
        prefix_sum[i] = current_sum
    
    # 全荷物の総重量 S
    total_sum = prefix_sum[-1]
    
    # 累積和の値を集合（set）に格納し、O(1) での検索を可能にする
    p_set = set(prefix_sum)
    
    # 使用できる荷台の個数を最大化するためには、各荷台の重量 w を最小化すればよい
    # 各荷台の重量 w は、必ずいずれかの累積和の値（prefix_sum[i]）と一致する必要がある
    # また、w は総重量 total_sum の約数でなければならない
    
    # 累積和は昇順に並んでいるため、順番に w として試すことで
    # 最初に見つかった有効な w が、荷台の個数 k = total_sum / w を最大化する
    for w in prefix_sum:
        # w が総重量を割り切れる場合のみ、均等な荷分けの可能性がある
        if total_sum % w == 0:
            k = total_sum // w
            
            # 荷台の個数 k は荷物の個数 n を超えることはできない
            if k > n:
                continue
            
            # 各荷台の重量が w であるとき、累積和の中に w, 2w, 3w, ..., kw が
            # すべて存在すれば、連続する荷物を組み合わせて重量 w のグループを k 個作ることができる
            # w と kw (= total_sum) は既に存在することが分かっているため、
            # 2w から (k-1)w までが累積和に含まれているかを確認する
            is_valid = True
            for j in range(2, k):
                if (j * w) not in p_set:
                    is_valid = False
                    break
            
            # 条件を満たす最小の w が見つかったら、その時の k を出力して終了
            if is_valid:
                print(k)
                return

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.