Tối ưu hóa chi phí phân bổ tài nguyên
Xem PDF
Điểm:
1700
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(N\) đối tượng được đánh số từ \(1\) đến \(N\). Ta cần phân bổ các số nguyên không âm \(x_1, x_2, \dots, x_N\) sao cho tổng của chúng đúng bằng \(S\):
\[\sum_{i=1}^N x_i = S\]
Với mỗi đối tượng \(i\), nếu ta chọn giá trị \(x_i \ge 0\), chi phí phát sinh là:
\[f_i(x_i) = a_i \cdot x_i^2 + b_i \cdot x_i\]
Trong đó \(a_i, b_i\) là các hệ số dương cho trước.
Hãy tìm giá trị nhỏ nhất có thể của tổng chi phí \(F = \sum_{i=1}^N f_i(x_i)\).
Input
- Dòng đầu tiên chứa hai số nguyên \(N\) và \(S\) (\(1 \le N \le 2 \cdot 10^5\), \(1 \le S \le 10^9\)).
- \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) (\(1 \le a_i \le 10^6\), \(0 \le b_i \le 10^6\)).
Output
- In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.
Example
Test 1
Input
3 5
1 2
2 1
3 0Output
21Note
Các giá trị \(x_i\) tối ưu là \(x_1 = 3, x_2 = 1, x_3 = 1\).
Tổng \(x_1 + x_2 + x_3 = 3 + 1 + 1 = 5\).
Chi phí tương ứng:
- \(f_1(3) = 1 \cdot 3^2 + 2 \cdot 3 = 15\)
- \(f_2(1) = 2 \cdot 1^2 + 1 \cdot 1 = 3\)
- \(f_3(1) = 3 \cdot 1^2 + 0 \cdot 1 = 3\)
Tổng chi phí \(= 15 + 3 + 3 = 21\).
Scoring
- Subtask 1 (100% điểm): \(1 \le N \le 2 \cdot 10^5\), \(1 \le S \le 10^9\), \(1 \le a_i \le 10^6\), \(0 \le b_i \le 10^6\).
Bình luận