Two Groups

Tác giả:

Dạng bài

Ngôn ngữ cho phép

C, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Output, Pascal, Prolog, Python, Scala

Điểm: 800 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số \(a\) gồm \(n\) phần tử. Hãy tìm cách chia dãy số này thành 2 dãy con liên tiếp \(s_1,s_2\) (có thể là dãy rỗng) sao cho:

Với mọi \(1 \le i \le n\), \(a_i\) thuộc đúng một nhóm.
Tổng \(|sum(s_1)|-|sum(s_2)|\) đạt giá trị lớn nhất có thể. Trong đó \(sum(s_1)\) thể hiện cho tổng tất cả các phần tử của dãy \(s_1\)

Dòng thứ nhất chứa số nguyên dương \(t\) \((t \le 10^3)\) - số testcase;
Mỗi testcase tiếp theo có dạng như sau:
- Dòng thứ nhất chứa số nguyên dương \(n\) \((n \le 10^3)\);
- Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) \((-10^9 \le a_i \le 10^9)\)

Test 1

Sample input

4
2
10 -10
4
-2 -1 11 0
3
2 3 2
5
-9 2 0 0 -4

Sample output

Explanation

Trong testcase thứ nhất, ta có thể chia thành hai dãy \(s_1=\{10\}\), \(s_2=\{-10\}\).
Trong testcase thứ hai, ta có thể chia thành hai dãy \(s_1=\{0;11;-1\}\), \(s_2=\{-2\}\)
Trong testcase thứ ba, ta có thể chia thành hai dãy \(s_1=\{2;3;2\}\), \(s_2=\{\}\)
Trong testcase thứ tư, ta có thể chia thành hai dãy \(s_1=\{-9;-4;0\}\), \(s_2=\{2;0\}\)

Bình luận