Overview

We split the sequence of packages into several contiguous segments (without changing the order) such that the total weight of each segment (each truck bed) is equal, and we want to find the maximum number of truck beds we can use.

Approach

Key Observation

If we use \(k\) truck beds, the total weight of each truck bed must be: - Let the overall sum be \(T=\sum H_i\) - Each truck bed’s weight \(S = T/k\)

Therefore, \(k\) must be a divisor of \(T\).

Furthermore, since the packages are split into contiguous segments, the split positions can be expressed using “prefix sums.”
Let the prefix sums be \(P_0=0,\,P_i=H_1+\cdots+H_i\). To create \(k\) segments each with weight \(S\), it is necessary and sufficient that

• \(S, 2S, 3S, \ldots, (k-1)S\)

all exist in the prefix sum set \(\{P_0,P_1,\ldots,P_N\}\).
(If they all exist, we can split at those positions so that each segment sum equals \(S\).)

Also, since each segment must contain at least one package, \(k \le N\).
Additionally, each segment sum \(S\) must be at least the maximum package weight \(\max(H_i)\), so: - \(S \ge \max(H_i)\) - That is, \(T/k \ge \max(H_i) \Rightarrow k \le T/\max(H_i)\)

Therefore, the values of \(k\) we need to check are limited to: - \(k \mid T\) - \(k \le \min\!\left(N,\left\lfloor T/\max(H_i)\right\rfloor\right)\)

Why a Naive Solution Is Too Slow

If we “try all \(k\) from largest to smallest” and scan the array each time, it can be close to \(O(N^2)\) in the worst case, which is too slow.
Instead, we use the following strategy: - Restrict candidate \(k\) values to “divisors of \(T\)” (there are few of them) - For each check, instead of scanning the array, we check “whether values are contained in the prefix sum set” (each check is lightweight)

Algorithm

1. Compute the total sum \(T=\sum H_i\) and the maximum value \(M=\max(H_i)\).
2. Build the prefix sums \(P_i\) and insert all of them into a set pref (including 0).
3. Factorize \(T\) and enumerate all its divisors.
4. Among the divisors, only keep those satisfying \(k \le k_{\max}=\min(N,\lfloor T/M\rfloor)\) as candidates, and try them in descending order.
5. For each candidate \(k\), let \(S=T/k\) and check using set lookups whether S, 2S, ..., (k-1)S are all contained in pref.
   • If all are contained, this \(k\) is the maximum, so output it and terminate.
6. If none work, \(k=1\) is always possible, so output 1.

(Example) - If \(H=[1,2,3,3,2,1]\), then \(T=12\). - For \(k=4\), \(S=3\). The prefix sums are \(0,1,3,6,9,11,12\), so \(3,6,9\) all exist — OK → a 4-way split is possible.

Complexity

• Time complexity:
  
  • Factorization: \(O(\sqrt{T})\)
    
  • Prefix sum construction: \(O(N)\)
    
  • Let \(d\) be the number of divisors. The total cost of checks is roughly \(O\!\left(\sum_{k\in \text{candidates}} k\right)\) (for each candidate \(k\), at most \(k-1\) set lookups)
    
  • Overall: \(O(\sqrt{T}+N+\sum k)\)
• Space complexity: \(O(N)\) (prefix sum set)

Implementation Notes

• Storing prefix sums in a set allows us to check “whether a split position exists” in \(O(1)\) average time.

• Pre-filtering with \(k_{\max}=\min(N,\lfloor T/\max(H_i)\rfloor)\) reduces unnecessary trials.

• By trying divisors in descending order and outputting the first successful one, we guarantee the “maximum number of truck beds.”

• Since the input can be large, we use sys.stdin.buffer.read() for fast reading.

  Source Code

import sys
import math


def factorize(n: int):
    factors = []
    cnt = 0
    while n % 2 == 0:
        n //= 2
        cnt += 1
    if cnt:
        factors.append((2, cnt))
    p = 3
    while p * p <= n:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            factors.append((p, cnt))
        p += 2
    if n > 1:
        factors.append((n, 1))
    return factors


def all_divisors_from_factors(factors):
    divs = [1]
    for p, e in factors:
        cur = []
        pe = 1
        for _ in range(e + 1):
            for d in divs:
                cur.append(d * pe)
            pe *= p
        divs = cur
    return divs


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    H = data[1:]

    total = sum(H)
    max_h = max(H)

    pref = set()
    s = 0
    pref.add(0)
    for h in H:
        s += h
        pref.add(s)

    kmax = min(N, total // max_h)  # S = total/k must satisfy S >= max_h
    factors = factorize(total)
    divs = all_divisors_from_factors(factors)

    candidates = [k for k in divs if k <= kmax]
    candidates.sort(reverse=True)

    for k in candidates:
        seg = total // k
        if seg < max_h:
            continue
        x = seg
        ok = True
        for _ in range(k - 1):
            if x not in pref:
                ok = False
                break
            x += seg
        if ok:
            print(k)
            return

    print(1)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.