Two Groups

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
dang7rickroll
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\)

Input

  • 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)\)

Output

  • Ứng với mỗi test case in ra giá trị \(|sum(s_1)|-|sum(s_2)|\) lớn nhất có thể.

Example

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 
0
8
7
11
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\}\)

Note

  • Nguồn: CF Round 832 div 2

Bình luận