累積和を \(S_i=\sum_{j=1}^{i}W_j\) と定めます。

\(k\) 台の荷台を使うことができるための必要十分条件は、 \(S_N\) が \(k\) の倍数、かつ、\(\frac{S_N}{k}, \frac{2S_N}{k},\dots,\frac{(k-1)S_N}{k}\) が全て \((S_1,\dots,S_N)\) に登場することです。

よって、 \(S\) を hash set で持ち、\(k\) を全探索することで、\(S_N\) の \(N\) 以下の約数の個数を \(f(S_N,N)\) として expected \(O(N f(S_N,N))\) 時間でこの問題を解くことができます。

今回の制約の下、

\(f(S_N,N)\leq f(S_N, 10^6)\leq \max_{n\leq 2\times 10^{14}}f(n,10^6) \)

であり、

\(\begin{aligned} \max_{n\leq 10^{12}}f(n,10^6) &\leq \max_{n\leq 10^{12}}f(n,\infty) \\ &= \max_{n\leq 10^{12}}\sigma_0(n)\\ &\leq 10^4 \end{aligned}\)

及び

\(\begin{aligned} \max_{10^{12} \leq n\leq 2 \times 10^{14}}f(n,10^6) & \leq \max_{10^{12} \leq n\leq 2 \times 10^{14}}f(n,\sqrt{n})\\ & \leq \max_{10^{12} \leq n \leq 2\times 10^{14}} \sigma_0(n)/2\\ & = 10080 \end{aligned}\)

であることから \(f(S_N,N) \leq 10080\) であり、十分高速です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> w(n);
  for(int i=0; i<n; i++) cin >> w[i];

  unordered_set<long long> s({0});
  long long sum = 0;
  for(int i=0; i<n; i++){
    sum += w[i];
    s.insert(sum);
  }

  for(int k=n; k>=1; k--){
    if(sum % k == 0){
      bool ok = true;
      for(int i=0; i<k; i++){
        ok &= s.contains(sum / k * i);
      }
      if(ok){
        cout << k << endl;
        return 0;
      }
    }
  }
}

実装例 (Python)

N = int(input())
W = list(map(int, input().split()))

S = set([0])
s = 0
for w in W:
  s += w
  S.add(s)

for k in range(N, 0, -1):
  if s % k == 0 and all((s // k * i in S) for i in range(k)):
    print(k)
    exit()