Trò Chơi Bánh Kem

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie và Elsie phát hiện một hàng gồm $N$ chiếc bánh ( $2 \leq N \leq 5 \cdot 10^{5}$ , $N$ chẵn) với kích thước $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Trò chơi diễn ra xen kẽ giữa hai người chơi:

Lượt Bessie: Chồng hai chiếc bánh liền kề thành một chiếc bánh có kích thước bằng tổng.
Lượt Elsie: Lấy chiếc bánh ở đầu trái hoặc đầu phải.

Khi chỉ còn một chiếc bánh, Bessie ăn nó và Elsie ăn tất cả bánh đã thu thập. Cả hai chơi tối ưu để tối đa hóa phần mình nhận được, Bessie đi trước.

Dữ liệu vào

Dòng đầu: $T$ ( $1 \leq T \leq 10$ ) là số test case.
Mỗi test case:
- Dòng $1$ : Số nguyên $N$ .
- Dòng $2$ : $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ .
Tổng $N$ qua tất cả test case không vượt quá $10^{6}$ .

Dữ liệu ra

Với mỗi test case, in ra hai số nguyên $b$ và $e$ - lượng Bessie và Elsie nhận được khi cả hai chơi tối ưu.

Ràng buộc

Test $2$ : Tất cả $a_{i}$ bằng nhau
Test $3$ : $N \leq 10$
Test $4$ - $7$ : $N \leq 5000$
Test $8$ - $11$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
2 4 40 30 20 10 4 10 20 30 40	60 40 60 40	Cả hai trường hợp, Bessie nhận 60 và Elsie nhận 40.

Bình luận

Không có bình luận tại thời điểm này.