Two Groups
Xem PDF
Đ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 -4Sample output
0
8
7
11Explanation
- 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
Ủa rồi là dấu cộng hay dấu trừ vậy, sao mà em hoang mang quá 😰
Hint (cho ai không có idea):
Ta thấy rằng để cho kết quả lớn nhất thì s1 chỉ có số dương, s2 chỉ có số âm. Sau đó ta tính tổng, hàm abs và trừ ra sẽ ra kết quả.