Cửa Hàng Tối Ưu

Buổi 13 — Chặt nhị phân đáp án Buổi 14 — Two Pointers & Sliding Window Buổi 15 — Prefix Sum & Difference Array Buổi 16 — Contest Chặng 2 prefix-sum
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Trên trục số có $N$ cửa hàng tại các vị trí $x_1, x_2, \ldots, x_N$ (đã sắp xếp tăng dần). Mỗi cửa hàng có trọng số (số lượng khách hàng) $w_i$. Cần chọn một vị trí (số nguyên) để đặt kho hàng sao cho tổng khoảng cách có trọng số $\sum_{i=1}^{N} w_i \cdot |pos - x_i|$ là nhỏ nhất.

In ra tổng khoảng cách có trọng số nhỏ nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ $(1 \le N \le 10^5)$.
  • $N$ dòng tiếp theo, mỗi dòng chứa $x_i$ và $w_i$ $(|x_i| \le 10^9, 1 \le w_i \le 10^9)$.
Dữ liệu ra
  • In ra tổng khoảng cách có trọng số nhỏ nhất.
Ví dụ
Input Output
3
1 1
2 1
3 1
2
3
1 1
3 2
5 1
6
Giới hạn
  • $1 \le N \le 10^5$
  • $|x_i| \le 10^9$
  • $1 \le w_i \le 10^9$
Draft saved