Equal Sum Subarrays
골드 I의견: 0
*Note: The time limit for this problem is 3s, 1.5x the default.*
FJ gave Bessie an array \(a\) of length \(N\)
(\(2\le N\le 500, -10^{15}\le a_i\le 10^{15}\)) with all \(\frac{N(N+1)}{2}\)
contiguous subarray sums distinct. For each index \(i\in [1,N]\), help Bessie
compute the minimum amount it suffices to change \(a_i\) by so that there are two
different contiguous subarrays of \(a\) with equal sum.
Problem credits: Benjamin Qi
SCORING
- Input 3: \(N\le 40\)
- Input 4: \(N \le 80\)
- Inputs 5-7: \(N \le 200\)
- Inputs 8-16: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\).
The next line contains \(a_1,\dots, a_N\) (the elements of \(a\), in order).
One line for each index \(i\in [1,N]\).
2
2 -32
3Decreasing \(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\).
3
3 -10 41
6
1Increasing \(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\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Gold
평가 및 의견
Equal Sum Subarrays
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Equal Sum Subarrays