Equal Sum Subarrays

题目描述

注意：本题时间限制为 3s，是默认值的 1.5 倍。 FJ 给了 Bessie 一个长度为 $N$ 的数组 $a$ （$2\le N\le 500, -10^{15}\le a_i\le 10^{15}$），并且它的全部 $\frac{N(N+1)}{2}$ 个连续子数组和两两不同。对于每个下标 $i\in [1,N]$，请帮助 Bessie 计算：至少需要将 $a_i$ 改变多少，才能使得 $a$ 中存在两个不同的连续子数组具有相同的和。

输入格式

第一行包含 $N$。 下一行包含 $a_1,\dots, a_N$（按顺序给出 $a$ 的元素）。

输出格式

对于每个下标 $i\in [1,N]$ 输出一行。

2
2 -3

2
3

3
3 -10 4

1
6
1

提示

将 $a_1$ 减少 $2$ 会使得 $a_1+a_2=a_2$。类似地，将 $a_2$ 增加 $3$ 会使得 $a_1+a_2=a_1$。 将 $a_1$ 增加或将 $a_3$ 减少 $1$ 会使得 $a_1=a_3$。 将 $a_2$ 增加 $6$ 会使得 $a_1=a_1+a_2+a_3$。 计分： 输入 3：$N\le 40$ 输入 4：$N \le 80$ 输入 5-7：$N \le 200$ 输入 8-16：无额外限制。 题目来源：Benjamin Qi

标签: USACO|2023|Gold

来源

USACO|2023|Gold