Chọn ĐTQG Bắc Ninh 2026 - Bài 1
Một công ty công nghệ cần xử lý lần lượt \(n\) tác vụ theo thứ tự đã cho. Tác vụ thứ \(i\) yêu cầu ít nhất \(a_i\) GB bộ nhớ trong (RAM) và \(b_i\) GB dung lượng lưu trữ (Disk).
Các tác vụ phải được chia thành đúng \(k\) lô gồm các tác vụ liên tiếp. Mỗi lô được xử lý trên một máy chủ có cấu hình cố định là \((x,y)\), trong đó \(x\) là dung lượng bộ nhớ trong và \(y\) là dung lượng lưu trữ. Máy chủ có thể xử lý tác vụ thứ \(i\) nếu \(a_i \le x\) và \(b_i \le y\).
Chi phí thuê một máy chủ cấu hình \((x,y)\) để xử lý một lô là \(x+y\), không phụ thuộc vào số lượng tác vụ trong lô. Sau khi hoàn thành lô, máy chủ được trả lại; nếu cần sử dụng cùng cấu hình cho một lô khác, công ty phải thuê lại từ đầu.
Hãy chia \(n\) tác vụ thành đúng \(k\) lô liên tiếp và lựa chọn cấu hình máy chủ cho từng lô sao cho tất cả các tác vụ đều được xử lý, đồng thời tổng chi phí thuê là nhỏ nhất.
Input
- Dòng đầu tiên chứa hai số nguyên dương \(n,k\) \((n \le 10^5\), \(k \le \min(n,100)\), \(n \cdot k \le 10^6)\) lần lượt là số tác vụ và số lô.
- Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((a_i \le 10^9)\).
- Dòng thứ ba chứa \(n\) số nguyên dương \(b_1,b_2,\ldots,b_n\) \((b_i \le 10^9)\).
Output
- In ra một số nguyên duy nhất là tổng chi phí thuê nhỏ nhất tìm được.
Example
Test 1
Input
6 3
4 4 2 3 1 1
2 1 3 3 7 6Output
20Note
Chia \(6\) tác vụ thành \(3\) lô liên tiếp là \([1,2]\), \([3,4]\), \([5,6]\). Tổng chi phí thuê là \((4+2)+(3+3)+(1+7)=20\).
Test 2
Input
6 3
8 3 3 1 7 6
3 9 6 9 7 7Output
37Note
Chia \(6\) tác vụ thành \(3\) lô liên tiếp là \([1]\), \([2,3,4]\), \([5,6]\). Tổng chi phí thuê là \((8+3)+(3+9)+(7+7)=37\).
Test 3
Input
4 2
1 4 5 1
1 1 1 1Output
8Note
Có \(2\) cách chia \(4\) tác vụ thành \(2\) lô cùng đạt chi phí nhỏ nhất là \(8\): \([1]\), \([2,3,4]\) hoặc \([1,2,3]\), \([4]\).
Scoring
- Subtask 1 (10% số điểm): \(k=2\).
- Subtask 2 (20% số điểm): \(n \le 100\).
- Subtask 3 (20% số điểm): \(100 < n \le 1000\).
- Subtask 4 (25% số điểm): \(b_1=b_2=\ldots=b_n=1\).
- Subtask 5 (25% số điểm): Không có ràng buộc bổ sung.