29784번 - Collecting Pancakes 서브태스크다국어

문제

Alice and Bob both have a sweet tooth, and they are going to play a game to collect pancakes. There are $\mathbf{N}$ pancake stacks lined up on the table labeled from 1ドル$ to $\mathbf{N}$. The $i$-th stack has exactly $\mathbf{A_i}$ pancakes. Alice and Bob are going to collect pancakes by alternating turns claiming full stacks. For the first turn, Alice must choose a stack labeled between $\mathbf{L_a}$ and $\mathbf{R_a},ドル inclusive, and claim it. Then, Bob must choose a stack labeled between $\mathbf{L_b}$ and $\mathbf{R_b},ドル inclusive, and different from the one chosen by Alice, and claim it.

In subsequent turns, each of them must choose an unclaimed stack that is adjacent to a stack they claimed themselves before. That is, for Alice to claim stack $i$ on one of her turns other than the first, she must have claimed either stack $i-1$ or stack $i+1$ in one of her previous turns. The same is true for Bob. If at some point there is no valid choice for either player, they skip that turn and claim no stack.

The game ends when every stack is claimed. At that point, Alice collects all pancakes from all stacks she claimed, and Bob collects all pancakes in all stacks he claimed.

Alice wants to get as many pancakes as possible for herself, and Bob wants to get as many pancakes as possible for himself. Can you help Alice find out the maximum number of pancakes she can collect if they both play optimally?

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of three lines.

The first line of each test case contains an integer $\mathbf{N},ドル representing the number of pancake stacks.

The second line contains $\mathbf{N}$ integers $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N},ドル where $\mathbf{A_i}$ denotes the number of pancakes in stack $i$.

The third line contains 4ドル$ integers $\mathbf{L_a},ドル $\mathbf{R_a},ドル $\mathbf{L_b},ドル and $\mathbf{R_b},ドル the inclusive ranges of pancake stack labels Alice and Bob can choose for their first turn, respectively.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of pancakes Alice can collect after playing the game optimally.

제한

• 1ドル \le \mathbf{T} \le 100$.
• 1ドル \le \mathbf{A_i} \le 10^9,ドル for all $i$.
• 1ドル \le \mathbf{L_a} \le \mathbf{R_a} \le \mathbf{N}$
• 1ドル \le \mathbf{L_b} \le \mathbf{R_b} \le \mathbf{N}$
• It is not the case that $\mathbf{L_a} \le \mathbf{L_b} = \mathbf{R_b} \le \mathbf{R_a}$. (Bob is guaranteed to be able to pick a stack for his first turn regardless of Alice's choice.)

Test Set 1 (4점)

• 2ドル \le \mathbf{N} \le 100$.

Test Set 2 (10점)

• 2ドル \le \mathbf{N} \le 10^5$.

힌트

In Sample Case #1, there are 5ドル$ pancake stacks with 30,ドル 50, 40, 20, 10$ pancakes in them. Alice can choose the first or second stack at the beginning of the game, and Bob can choose the fourth or fifth stack to begin with. One way in which they both play optimally is:

1. At the beginning, Alice claims stack 2ドル,ドル then Bob claims stack 4ドル$.
2. Alice claims stack 3ドル$ in her second turn, then Bob claims stack 5ドル$ in his second turn.
3. Alice claims stack 1ドル$ in her third turn, then the game ends because all stacks have been claimed.

At the end of the game, Alice claimed stacks 1,ドル 2,ドル and 3ドル$ and Bob claimed stacks 4ドル$ and 5ドル$. The number of pancakes Alice collects is 30ドル+50+40=120$.

In Sample Case #2, one way of optimal play is:

1. At the beginning, Alice claims stack 3ドル,ドル then Bob claims stack 2ドル$.
2. Alice claims stack 4ドル$ in her second turn, then Bob claims stack 1ドル$ in his second turn.
3. Alice claims stack 5ドル$ in her third turn, then the game ends because all stacks have been claimed.

The number of pancakes Alice collects is 80ドル+10+10=100$.

In Sample Case #3, both can claim any stack in their first turn. Since stack 1ドル$ is more valuable than everything else combined, Alice claims it before Bob does. Then, Bob can claim stack 2ドル,ドル making Alice have to skip all her subsequent turns. Alice still finishes with 90ドル$ pancakes and Bob with just 30ドル$.