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


  • 6
    flo    11:21 a.m. 28 Tháng 1, 2023

    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ả.


    • 0
      nob_Python69    7:56 a.m. 26 Tháng 5, 2024

      ko dc đâu b ơi, cái test 2 của sample có dãy s1 chứa cả số âm và dương kìa.


      • 0
        dang7rickroll    8:00 a.m. 26 Tháng 5, 2024

        Giờ bạn chuyển số \(-1\) qua tập \(\{-2\}\) (tức là thành hai tập \(\{0;11\}\) và \(\{-1;-2\}\)) thì đáp án vẫn là \(8\) mà =))


        • 0
          lehongduc    8:33 a.m. 17 Tháng 11, 2024

          trung bình test của những bài tham lam =)

      1 bình luận nữa