/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は引っ越し業者でアルバイトをしています。今日の仕事は、倉庫に一列に並んでいる N 個の荷物をトラックに積み込むことです。左から i 番目の荷物の重さは W_i kg です。
トラックには必要なだけいくつでも荷台を使うことができます。高橋君は、荷物を荷台に分配する際、以下のルールに従います。
ルール:
N 個の荷物の列を、連続する 1 つ以上の荷物からなるグループにすき間なく分割し、各グループをそれぞれ 1 つの荷台に積み込む。すなわち、各荷物はちょうど 1 つの荷台に積まれ、同じ荷台に積まれる荷物は元の列において連続している。さらに、すべての荷台に積まれた荷物の総重量が互いに等しくなければならない。
高橋君は、できるだけ多くの荷台を使いたいと考えています（荷台が多いほど各荷台の重量が軽くなり、積み下ろしが楽になるためです）。
上のルールを満たすように荷物を分配するとき、使用できる荷台の個数の最大値を求めてください。
なお、荷台を 1 つだけ使い、すべての荷物をその荷台に積む分配は常にルールを満たすため、条件を満たす分配は必ず存在します。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9
- 入力はすべて整数
入力
N W_1 W_2 \ldots W_N
- 1 行目には、荷物の個数を表す整数 N が与えられる。
- 2 行目には、左から i 番目の荷物の重さを表す N 個の整数 W_1, W_2, \ldots, W_N がスペース区切りで与えられる。
出力
使用できる荷台の個数の最大値を 1 行で出力せよ。
入力例 1
6 1 2 3 3 2 1
出力例 1
4
入力例 2
10 2 4 2 2 6 4 2 2 8 8
出力例 2
5
入力例 3
15 1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000
出力例 3
12
Score : 366 pts
Problem Statement
Takahashi is working part-time at a moving company. Today's job is to load N packages lined up in a row in a warehouse onto a truck. The weight of the i-th package from the left is W_i kg.
The truck has as many platforms as needed. When distributing the packages onto the platforms, Takahashi follows the following rule.
Rule:
Divide the row of N packages into groups of one or more consecutive packages with no gaps, and load each group onto exactly one platform. That is, each package is loaded onto exactly one platform, and packages loaded onto the same platform are consecutive in the original row. Furthermore, the total weight of packages on every platform must be equal.
Takahashi wants to use as many platforms as possible (because the more platforms there are, the lighter each platform's load becomes, making loading and unloading easier).
Find the maximum number of platforms that can be used when distributing the packages according to the above rule.
Note that using just one platform and loading all packages onto it always satisfies the rule, so a valid distribution always exists.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9
- All inputs are integers
Input
N W_1 W_2 \ldots W_N
- The first line contains an integer N representing the number of packages.
- The second line contains N integers W_1, W_2, \ldots, W_N separated by spaces, where the i-th integer represents the weight of the i-th package from the left.
Output
Print the maximum number of platforms that can be used, on a single line.
Sample Input 1
6 1 2 3 3 2 1
Sample Output 1
4
Sample Input 2
10 2 4 2 2 6 4 2 2 8 8
Sample Output 2
5
Sample Input 3
15 1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000
Sample Output 3
12