[고등부] 2023 KOI 대비 모의고사 (4월 1주차)

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

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

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

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

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

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

2
keyboard_return
2space_bar -3

2
keyboard_return
3

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

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

3
keyboard_return
3space_bar -10space_bar 4

1
keyboard_return
6
keyboard_return
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이 된다.

로그인해야 코드를 작성할 수 있어요.