레이팅 미적용베시와 엘시는 한 줄로 놓인 \(N\)개의 케이크를 발견했다 \((2 \leq N \leq 5\cdot 10^5\), \(N\)은 짝수\()\). 케이크의 크기는 순서대로 \(a_1,a_2,\dots,a_N\)이다 (\(1\le a_i\le 10^9\)).
두 소 모두 최대한 많이 먹고 싶어 한다. 하지만 매우 교양 있는 소들이기에, 게임을 해서 케이크를 나누기로 했다! 게임은 두 소가 번갈아 차례를 가지며 진행된다. 각 차례는 다음 중 하나로 이루어진다.
- 베시가 인접한 두 케이크를 골라 쌓아서, 두 크기의 합과 같은 크기의 새 케이크를 만든다.
- 엘시가 가장 왼쪽 또는 가장 오른쪽 케이크를 골라 자신의 보관함에 넣는다.
케이크가 하나만 남으면 베시가 그것을 먹고, 엘시는 자신의 보관함에 있는 케이크를 모두 먹는다. 두 소가 모두 자신이 먹는 케이크의 양을 최대화하도록 최적으로 플레이하고 베시가 먼저 시작한다면, 각 소는 케이크를 얼마나 먹게 될까?
문제 제공: Linda Zhao, Agastya Goel, Gavin Ye
배점
- 입력 2: 모든 \(a_i\)가 같다.
- 입력 3: \(N\le 10\)
- 입력 4-7: \(N\le 5000\)
- 입력 8-11: 추가 제약 없음.
문제 제공: Linda Zhao, Agastya Goel, Gavin Ye
각 입력은 \(T\)(\(1\le T\le 10\))개의 독립적인 테스트 케이스로 이루어진다. 입력 내 모든 \(N\)의 합이 \(10^6\)을 넘지 않음이 보장된다.
각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 \(N\)이 주어진다. 다음 줄에 공백으로 구분된 \(N\)개의 정수 \(a_1,a_2,\ldots,a_N\)이 주어진다.
각 테스트 케이스에 대해, 두 소가 모두 최적으로 플레이할 때 베시와 엘시가 각각 먹게 되는 케이크의 양 \(b\)와 \(e\)를 한 줄에 출력한다.
2
4
40 30 20 10
4
10 20 30 4060 40
60 40For the first test case, under optimal play,
- Bessie will stack the middle two cakes. The cakes now have sizes \([40,50,10]\).
- Elsie will eat the leftmost cake. The remaining cakes now have sizes \([50,10]\).
- Bessie stacks the remaining two cakes.
Bessie will eat \(30+20+10=60\) cake, while Elsie will eat \(40\) cake.
The second test case is the reverse of the first, so the answer is the same.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Silver