JOI 2024 - Ski 2
Xem PDFÔng JOI quản lý một khu trượt tuyết nổi tiếng trên cao nguyên IOI. Để kỷ niệm \(15\) năm ngày khai trương, ông quyết định xây dựng một khu trượt tuyết mới trên cao nguyên KOI nằm liền kề.
Cao nguyên KOI có \(N\) địa điểm, được đánh số từ \(1\) đến \(N\). Hiện tại, địa điểm \(i\) (\(1 \le i \le N\)) có độ cao \(H_i\) mét, và chưa có đường trượt nào nối các địa điểm. Ngoài ra, tại mỗi địa điểm đã có sẵn một thiết bị kết nối chưa được sử dụng.
Mục tiêu của ông JOI là xây khách sạn KOI tại một trong \(N\) địa điểm, sau đó xây các đường trượt sao cho có thể trượt xuống khách sạn từ bất kỳ địa điểm nào. Cụ thể, ông thực hiện các bước theo thứ tự sau:
- Thực hiện việc đắp đất dưới đây không hoặc nhiều lần: chọn một địa điểm \(i\) và tăng độ cao của nó thêm \(1\) mét. Chi phí mỗi lần là \(K\).
- Chọn một trong \(N\) địa điểm để xây khách sạn KOI.
- Thực hiện việc mở rộng dưới đây không hoặc nhiều lần: chọn một địa điểm \(i\) và xây thêm một thiết bị kết nối tại đó. Chi phí mỗi lần là \(C_i\).
- Với mỗi địa điểm trong \(N-1\) địa điểm không có khách sạn, thực hiện việc xây dựng sau: gọi số thứ tự của địa điểm này là \(i\). Chọn một địa điểm khác \(j\) có độ cao thấp hơn hẳn địa điểm \(i\), rồi dùng một thiết bị kết nối chưa sử dụng tại địa điểm \(j\) để xây một đường trượt một chiều từ \(i\) đến \(j\). Nếu không tồn tại địa điểm thấp hơn hẳn \(i\) và còn thiết bị kết nối chưa sử dụng, mục tiêu không thể đạt được.
Chi phí xây dựng khu trượt tuyết là tổng chi phí đắp đất và mở rộng đã thực hiện.
Hãy viết chương trình tìm chi phí xây dựng nhỏ nhất khi biết thông tin của mỗi địa điểm và chi phí \(K\) cho một lần đắp đất.
Dữ liệu vào
Đọc từ đầu vào chuẩn theo định dạng:
N K
H_1 C_1
H_2 C_2
...
H_N C_N
Dữ liệu ra
In một dòng ra đầu ra chuẩn chứa chi phí nhỏ nhất để xây dựng khu trượt tuyết.
Ràng buộc
- \(1 \le N \le 300\).
- \(1 \le K \le 10^9\).
- \(0 \le H_i \le 10^9\) (\(1 \le i \le N\)).
- \(1 \le C_i \le 10^9\) (\(1 \le i \le N\)).
- Tất cả các giá trị đầu vào đều là số nguyên.
Phân nhóm
- 5 điểm: \(K \ge 100\,000\), \(H_i \le 300\) và \(C_i \le 100\) với mọi \(1 \le i \le N\).
- 12 điểm: \(H_1 \le H_i\), \(C_1 \le C_i\) và \(H_i \le 300\) với mọi \(1 \le i \le N\).
- 9 điểm: \(N \le 10\) và \(H_i \le 10\) với mọi \(1 \le i \le N\).
- 33 điểm: \(N \le 40\) và \(H_i \le 40\) với mọi \(1 \le i \le N\).
- 27 điểm: \(H_i \le 300\) với mọi \(1 \le i \le N\).
- 14 điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
5 2
0 6
1 1
0 5
2 1
1 2Output
8Giải thích
Ví dụ, có thể xây khu trượt tuyết như sau:
- Đắp đất hai lần tại địa điểm \(1\) và một lần tại địa điểm \(5\), tốn tổng cộng \(2\times(2+1)=6\). Độ cao các địa điểm theo thứ tự từ \(1\) trở đi trở thành \(2,1,0,2,2\) mét.
- Xây khách sạn KOI tại địa điểm \(3\).
- Mở rộng hai lần tại địa điểm \(2\), tốn tổng cộng \(1\times2=2\). Số thiết bị kết nối tại các địa điểm theo thứ tự từ \(1\) trở đi trở thành \(1,3,1,1,1\).
- Xây bốn đường trượt: từ \(1\) đến \(2\), từ \(2\) đến \(3\), từ \(4\) đến \(2\), và từ \(5\) đến \(2\).
Tổng chi phí là \(6+2=8\). Không thể xây khu trượt tuyết với chi phí không quá \(7\), nên kết quả là 8.
Ví dụ này thỏa mãn các ràng buộc của bài toán con \(3,4,5,6\).
Ví dụ 2
Input
5 100000
0 6
1 1
0 5
2 1
1 2Output
100010Giải thích
Ví dụ này chỉ khác ví dụ \(1\) ở giá trị \(K\).
Ví dụ này thỏa mãn các ràng buộc của bài toán con \(1,3,4,5,6\).
Ví dụ 3
Input
8 8
0 36
1 47
2 95
0 59
1 54
0 95
1 87
2 92Output
108Giải thích
Ví dụ này thỏa mãn các ràng buộc của bài toán con \(2,3,4,5,6\).
Nguồn
Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ nhất, do Ủy ban Olympic Tin học Nhật Bản (JCIOI) cung cấp. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2024 - Tuyển chọn mùa xuân - Ngày 1 (21 Tháng ba, 2024)
Bình luận