Trò chơi với ngọc (Chọn ĐT'20-21)

Xem PDF

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

Tí và Tèo rất thích chơi đùa với những viên ngọc. Hôm nay hai bạn có n viên ngọc trên bàn. Như vạn vật trên đời, mỗi viên ngọc có một vẻ đẹp riêng trong mắt mỗi người. Vì vậy, để giữ tình bạn thân thiết, Tí Tèo quyết định rằng, viên ngọc thứ \(i\) sẽ có vẻ đẹp \(a_i\) đối với Tí và \(b_i\) đối với Tèo. Tí và Tèo bắt đầu trò chơi như sau: hai bạn sẽ thay phiên bốc một viên ngọc trên bàn về phía mình. Sau khi bốc hết ngọc, điểm số của mỗi bạn sẽ là tổng vẻ đẹp các viên ngọc mà bạn đó lấy về phần mình.

Ví dụ nếu Tí bốc các viên 1, 3 và Tèo bốc các viên 2, 4 thì Tí được \(a_1+a_3\) điểm còn Tèo được \(b_2+b_4\) điểm. Mục tiêu của trò chơi là làm cho tổng điểm của mình trừ tổng điểm đối phương càng lớn càng tốt. Nói cách khác, đặt \(X\) là tổng điểm của Tí trừ tổng điểm của Tèo. Tí muốn \(X\) càng lớn càng tốt, còn Tèo muốn \(X\) càng nhỏ càng tốt. Biết rằng Tí đi trước và cả hai đều chơi tối ưu.

Yêu cầu: Hãy tính tổng điểm của Tí trừ tổng điểm của Tèo sau khi trò chơi kết thúc.

Input

  • Dòng 1 chứa số nguyên dương \(n\).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n\).
  • Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,…,b_n\).

Output

  • Ghi ra số nguyên là kết quả bài toán.

Constraints

  • \(1\leq n\leq 10^5\)
  • \(0\leq a_i\leq 10^9\) với \(1\leq i\leq n\)
  • \(0\leq b_i\leq 10^9\) với \(1\leq i\leq n\)

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(a_i=b_i\) với mọi \(1\leq i\leq n\).
  • Subtask \(2\) (\(40\%\) số điểm): \(n\leq 20\).
  • Subtask \(3\) (\(20\%\) số điểm): \(n\leq 10^3\).
  • Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3
10 20 30
10 20 30 
Output
20

Test 2

Input
2
10 20
20 10  
Output
0

Test 3

Input
4
10 10 10 20
20 20 20 30
Output
-10
Note
  • Trong ví dụ 1, Tí bốc viên ngọc thứ 3 trước. Sau đó Tèo bốc viên thứ 2 rồi Tí bốc viên thứ 1 còn lại. Như vậy Tí được \(40\) điểm, còn Tèo được \(20\) điểm. Hiệu là \(20\).
  • Trong ví dụ 2, dù Tí bốc viên thứ 1 hay thứ 2 thì hai bạn cũng sẽ bằng điểm nhau.
  • Trong ví dụ 3, Tí bốc viên thứ 4 trước. Tèo bốc viên thứ 3. Tí bốc viên thứ 2 rồi Tèo bốc viên thứ 1. Hiệu của 2 bạn là: \((20 + 10) - (20 + 20) = -10\).

Bình luận

Không có bình luận nào.