문제
한글이와 정올이는
둘은 모두 최대한 많이 먹고 싶어 한다. 때문에, 그들은 케이크를 나누기 위해 게임을 하기로 했다! 게임은 두 사람이 차례대로 진행한다. 각 턴은 다음과 같이 이루어진다:
한글이는 두 개의 인접한 케이크를 선택하고 그것들을 쌓아서 크기 합이 새로운 케이크를 만든다.
이때, 하나의 케이크만 남으면 한글이가 그 케이크를 먹고 게임은 종료된다.
그 다음 정올이는 가장 왼쪽 또는 가장 오른쪽에 있는 케이크를 골라서 먹는다.
두 사람이 최적의 전략을 사용하여 최대한 많은 케이크를 먹을 때, 한글이와 정올이가 각각 얼마나 많은 케이크를 먹을지 알아보자.
입력
입력은 T개의 테스트 케이스로 이루어진다(1 ≤T≤ 10). 각 테스트 케이스는 다음과 같이 주어진다:
첫 번째 줄에
N 이 주어진다. (2 ≤ N ≤ 500,000 ,N 은 짝수)두 번째 줄에
N 개의 공백으로 구분된 정수a_1, a_2, ..., a_N 이 주어진다. (1 ≤ a_i ≤ 10^9 )
모든 테스트 케이스의 N의 합은 106을 넘지 않는다.
출력
각 테스트 케이스에 대해 한글이와 정올이가 먹는 케이크의 양을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | 모든 |
| #2 | 20점 | |
| #3 | 30점 | |
| #4 | 40점 | 추가 제약 조건 없음 |
예제1
2
4
40302010
4
10203040
6040
6040
첫 번째 테스트 케이스를 한글이와 정올이가 모두 최적의 플레이를 한다면 아래와 같이 진행될 수 있다.
한글이는 중앙의 두 케이크를 합쳐
[40,50,10] 와 같은 세 케이크가 남게 된다.정올이는 왼쪽의 케이크를 먹어 남은 케이트의 사이즈는
[50,10] 가 된다.남은 두 케이크를 하나로 합쳐 한글이가 먹는다.