← 返回题目列表

AtCoder · awc0071_c

C. 均等负载分配

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥在一家搬家公司做兼职。今天的工作是加载 N 包裹在仓库里排成一排,装到卡车上。的重量 i左边第一个包是 W_i 公斤。

卡车根据需要拥有任意多个平台。在将软件包分发到平台上时,高桥遵循以下规则。

规则:

划分行 N 打包成 一组或多个连续包裹 没有间隙,并将每一组加载到一个平台上。即每个包都被加载到同一个平台上,并且加载到同一平台上的包在原始行中是连续的。此外, 每个平台的包裹总重量必须相等.

高桥希望使用尽可能多的平台(因为平台越多,每个平台的负载就越轻,装卸变得更容易)。

根据上述规则求出分发包时可以使用的最大平台数。

请注意,仅使用一个平台并将所有包加载到该平台上始终满足规则,因此始终存在有效的发行版。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9
  • 所有输入均为整数

输入

N
W_1 W_2 \ldots W_N
  • 第一行包含一个整数 N 代表包裹数量。
  • 第二行包含 N 整数 W_1, W_2, \ldots, W_N 用空格分隔,其中 i- 第一个整数表示权重 i左边第一个包。

输出

在一行上打印可以使用的最大平台数。


示例输入 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