Bài toán khoản cách 2
Xem PDF
Điểm:
1100
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Trong một cửa hàng đá quý, có \(n\) túi vàng được trưng bày. Mỗi túi vàng thứ \(i\) có hai thông số quan trọng: trọng lượng \(w_i\) và giá trị \(v_i\).
Để đánh giá sự đa dạng của bộ sưu tập, người chủ cửa hàng định nghĩa "độ chênh lệch" giữa hai túi vàng \(x\) và \(y\) bất kỳ là tổng sự khác biệt về trọng lượng và giá trị của chúng:
\[|w_x - w_y| + |v_x - v_y|\]
Nhiệm vụ của bạn là giúp chủ cửa hàng tính tổng độ chênh lệch của tất cả các cặp túi vàng có trong cửa hàng. Nói cách khác, bạn cần tính giá trị của biểu thức:
\[S = \sum_{1 \le x < y \le n} (|w_x - w_y| + |v_x - v_y|)\]
Input
- Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
- \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i\) và \(v_i\) (\(0 \le w_i, v_i \le 10^6\)) lần lượt là trọng lượng và giá trị của túi vàng thứ \(i\).
Output
- Một số nguyên duy nhất là tổng độ chênh lệch của tất cả các cặp túi vàng.
Example
Test 1
Input
3
1 2
3 4
5 6Output
16Note
Các cặp túi vàng \((x, y)\) có độ chênh lệch là:
- Cặp (1, 2): \(|1 - 3| + |2 - 4| = 2 + 2 = 4\)
- Cặp (1, 3): \(|1 - 5| + |2 - 6| = 4 + 4 = 8\)
- Cặp (2, 3): \(|3 - 5| + |4 - 6| = 2 + 2 = 4\)
Tổng cộng: \(4 + 8 + 4 = 16\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^3\).
- Subtask \(2\) (\(70\%\) số điểm): \(n \le 2 \cdot 10^5\).
Bình luận