Page not loading? Try clicking here.
Placeholder

#5506

합이 같은 부분수열 (Equal Sum Subarrays) 3s 128MB

Problems

N*(N+1)/2개의 합이 다른 연속 부분수열을 갖는 길이 N의 수열 A가 주어졌을 때,

인덱스 i∈[1,N]에 대하여, A_i의 값을 최소 얼마나 더하거나 빼야 두 개의 다른 연속 부분수열의 합이 같아지는지 출력하시오.​​


Input

첫 번째 줄에 N이 입력된다 (2≤N≤500)​.

두 번째 줄에 수열 A의 원소 A_1, \space A_2, \space ..., \space A_N 이 입력된다 (-10^{15}≤A_i≤10^{15}​)​​.


Output

각 i (i∈[1,N]) 번째 줄에 A_i의 값을 최소 얼마나 더하거나 빼야 두 개의 다른 연속 부분수열의 합이 같아지는지 출력하시오.​​.​


Example #1

2

2 -3
2

3

A_1을 2 감소 시키면 A_1+A_2=A_2가 된다.

A_2를 3 증가 시키면 A_1+A_2=A_1이 된다.


Example #2

3

3 -10 4
1

6

1

A_1을 1 증가 시키면 A_1=A_3이 된다.

A_2를 6 증가 시키면 A_1=A_1+A_2+A_3​이 된다.

A_3를 1 감소 시키면 A_1=A_3​이 된다.



Source

USACO 2023 February Gold

You must sign in to write code.