#PU1305. USACO 2023 February Contest, Gold — Problem 1. Equal Sum Subarrays

    ID: 1406 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb23来源:usaco.orgscoring:equal_test_cases枚举哈希

USACO 2023 February Contest, Gold — Problem 1. Equal Sum Subarrays

USACO 2023 February Contest, Gold — Problem 1. Equal Sum Subarrays

题目描述

Note: The time limit for this problem is 3s, 1.5x the default. FJ gave Bessie an array aa of length NN (2≤N≤500,−1015≤ai≤10152\le N\le 500, -10^{15}\le a_i\le 10^{15}) with all N(N+1)2\frac{N(N+1)}{2} contiguous subarray sums distinct. For each index i∈[1,N]i\in [1,N], help Bessie compute the minimum amount it suffices to change aia_i by so that there are two different contiguous subarrays of aa with equal sum.

输入格式

The first line contains NN. The next line contains a1,…,aNa_1,\dots, a_N (the elements of aa, in order).

输出格式

One line for each index i∈[1,N]i\in [1,N].

数据范围

(见题面原文)

样例

样例 1

2
2 -3
2
3
Decreasing $a_1$ by $2$ would result in $a_1+a_2=a_2$. Similarly, increasing
$a_2$ by $3$ would result in $a_1+a_2=a_1$.

样例 2

3
3 -10 4
1
6
1
Increasing $a_1$ or decreasing $a_3$ by $1$ would result in $a_1=a_3$.
Increasing $a_2$ by $6$ would result in $a_1=a_1+a_2+a_3$.