Gửi bài giải
Điểm:
0,62 (OI)
Giới hạn thời gian:
13.5s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho mô hình bãi cỏ có dạng bảng chữ nhật ~2 \times B~ ~(1 \le B \le 15 000 000)~, trong đó một số ô có con bò đang ăn cỏ. Có tất cả ~N~ con bò ~(1 \le N \le 1000)~ trên bãi cỏ. Ví dụ:
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
| | cow | | | | cow | cow | cow | cow |
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
| | cow | cow | cow | | | | | |
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bác John muốn dùng ~K (1 \le K \le N)~ cái chuồng hình chữ nhật để che phủ đàn bò, sao cho tổng diện tích được phủ là nhỏ nhất. Không có hai chuồng nào được nằm đè lên nhau. Hiển nhiên, các chuồng phải che phủ hết các ô có bò.
Ví dụ, trong hình trên nếu ~K=2~, lời giải tối ưu bao gồm một chuồng kích thước ~2\times 3~ và một chuồng kích thước ~1 \times 4~. Tổng diện tích được phủ là ~10~.
Input
Dòng đầu tiên chứa một số nguyên ~t~ là số bộ test. Mỗi bộ test có dạng:
- Dòng ~1~: ~N, K, B~
- Dòng ~2 \dots N+1~: chức tọa độ của các con bò, trong phạm vi ~(1,1)~ đến ~(2,B)~. Không có ô nào chứa hơn ~1~ con bò.
Output
Với mỗi test, in ra tổng diện tích nhỏ nhất cần phủ.
Sample Input
1
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
Sample Output
10
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.