Overview

A problem where you divide consecutive items into groups such that the total weight of each group is equal, and you need to find the maximum number of groups possible.

Analysis

In this problem, we must partition items into consecutive subsequences such that the sum of each subsequence is equal. We want to find the maximum number of such partitions.

First, if all groups have the same sum, that sum must be a divisor of the total sum \(S\). In other words, if we divide into \(d\) groups, the sum of each group must be \(S/d\).

Therefore, we should try possible group counts by checking divisors of \(S\) from largest to smallest. Since the more groups there are, the smaller each group’s sum becomes, checking from the largest divisor first means the first valid one we find is the answer.

A naive approach (e.g., trying all possible ways to partition) would have very large computational complexity and wouldn’t finish in time. However, the number of divisors of \(S\) is at most a few hundred even when \(S\) is up to about \(2 \times 10^{14}\), so it can be processed efficiently.

For each divisor \(d\), we simulate whether the partition is actually possible. That is, we accumulate sums from the beginning, count when the sum reaches \(S/d\), and verify while being careful that the sum doesn’t exceed \(S/d\).

Algorithm

1. Compute the total sum \(S\).
2. Find all divisors of \(S\) (trial division up to \(\sqrt{S}\) is sufficient).
3. Sort the divisors in descending order.
4. For each divisor \(d\), try the following:
   • Target sum for each group: target = S / d
   • Accumulate the sum from the left; reset when it reaches target.
   • If the sum exceeds target, it’s impossible.
   • If exactly d groups are formed by the end, that’s the answer.
5. Output the first \(d\) that satisfies the condition.

Complexity

• Time complexity: \(O(\sqrt{S} + N \cdot d_{\text{max}})\)
  • \(O(\sqrt{S})\) for enumerating divisors, and at worst \(O(N)\) for the simulation per divisor.
• Space complexity: \(O(\sqrt{S})\)
  • Size of the list storing divisors.

Implementation Notes

• Divisors can be efficiently found with a loop up to \(\sqrt{S}\).
• By sorting divisors in descending order and trying from the largest candidate, we can return immediately when the condition is first satisfied.
• In each simulation, check whether the number of groups matches while being careful that the current sum doesn’t exceed the target.

## Source Code

```python
import sys
import math

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    H = list(map(int, data[1:N+1]))
    
    total = sum(H)
    if N == 1:
        print(1)
        return
    
    # 約数を大きい順に試す
    divisors = []
    for i in range(1, int(math.sqrt(total)) + 1):
        if total % i == 0:
            divisors.append(i)
            if i != total // i:
                divisors.append(total // i)
    
    divisors.sort(reverse=True)
    
    # 各約数について、分割可能かチェック
    for d in divisors:
        target = total // d
        count = 0
        current_sum = 0
        i = 0
        while i < N:
            current_sum += H[i]
            if current_sum == target:
                count += 1
                current_sum = 0
            elif current_sum > target:
                break
            i += 1
        if current_sum == 0 and count == d:
            print(d)
            return

if __name__ == "__main__":
    main()

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