페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2614

[고등부] 2025 KOI 1차대회 대비 파이널 모의고사

행복한 수열
서브태스크
10초 1024MB

문제

F(B, L, R)은 수열 B의 L번째 값부터 R번째 값으로 이루어진 부분 수열의 합이라 정의한다.

  • F(B, L, R) = B_L + B_{L+1} + \cdots + B_R

길이가 K인 수열 C의 모든 접두사 합(prefix sum)이 음수가 아닌 경우, 수열 C를 행복한 수열이라고 부른다.

  • F(C, 1, 1), F(C, 1, 2), \dots, F(C, 1, K)가 모두 음수가 아님을 의미한다.

길이 \mathbf{N} 의 수열 \mathbf{A}가 주어졌을 때, 해당 수열 \mathbf{A}에 있는 모든 행복한 수열이 될 수 있는 연속한 부분 수열의 합계를 더한 결과를 구하는 프로그램을 작성하시오.


입력

첫 번째 줄에는 테스트 케이스의 수 \mathbf{T}가 주어진다. (1 \le T \le 100)

각 \mathbf{T} 테스트 케이스는 아래와 같이 구성된다:

  • 첫 줄에 정수 \mathbf{N}이 주어진다.

  • 그 다음 줄에는 \mathbf{N}개의 정수 \mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}이 주어진다. (-800 \le \mathbf{A_i} \le 800)


출력

각 테스트 케이스에 대해 "Case #x: y"를 출력한다.

  • x는 1부터 시작하며 테스트 케이스의 번호를 의미한다.

  • y는 수열 \mathbf{A}의 연속한 부분 수열 중 행복한 수열의 합을 모두 더한 결과를 의미한다.


부분문제

번호 점수 조건
#130점

1\le N\le 200

#270점

최대 30개의 테스트 케이스에 대하여: 1 \le N \le 4 \cdot 10^5

나머지 테스트 케이스에 대하여: 1 \le N \le 200


예제 

2
5
1 -2 3 -2 4
3
1 0 3
Case #1: 14
Case #2: 12

Case #1: 행복한 수열은 [1], [3], [3, -2], [3, -2, 4],[4]가 존재하며, 각각의 합은 1, 3, 1, 5,4이기에, 그 총합은 14이다.

Case #2: 행복한 수열은 [1], [1, 0], [1, 0, 3], [0], [0, 3], [3]이 존재하며, 각각의 합은 1, 1, 4, 0, 3, 3이기에, 그 총합은 12이다.

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