DTOGRADA - Sơn tường
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Matija muốn sơn lại hàng rào nhà mình. Hàng rào của anh ấy được ghép bởi N tấm ván liên tiếp, mỗi tấm rộng 1 cm và có chiều cao khác nhau. Để sơn nhanh chóng và dễ dàng hơn, anh ấy đã mua "Super Pain Roller Deluxe" (một cây lăn xịn). Cây lăn có chiều rộng x cm. Mỗi lần dùng, anh ấy phải để cây lăn chạm vào bức tường hoàn toàn, nếu không sẽ không sơn được gì cả. Mặt khác, lúc nào cũng phải để cho cây lăn song song với mặt đất. Nói cách khác, anh ấy sẽ chọn ra x tấm ván liên tiếp và sơn từ dưới lên đến độ cao của tấm ván thấp nhất trong x tấm ván đó.
Tuy nhiên, cây lăn không thể giúp Matija sơn hết được hàng rào. Phần diện tích còn lại không thể sơn bằng cây lăn, anh ấy sẽ sơn bằng cọ nhỏ. Hãy giúp anh ấy tính xem phần diện tích phải sơn bằng cọ nhỏ nhất có thể là bao nhiêu, và số lần dùng cây lăn ít nhất để đạt được điều đó.
Input
- Dòng đầu ghi số nguyên N (1 ≤ N ≤ 10 6 ) là số tấm ván cần phải sơn và số nguyên X (1 ≤ X ≤ 10 5 ).
- Dòng tiếp theo ghi N số nguyên dương (mỗi số không quá 10 6 ) mô tả chiều cao của từng tấm ván.
Output
- Dòng thứ nhất ghi diện tích nhỏ nhất phải sơn bằng cọ.
- Dòng thứ hai ghi số lần dùng cây lăn ít nhất để đạt được diện tích đó.
Example
Input:
5 3
5 3 4 4 5
Output:
3
2
- Người up: khanhptnk
- Nguồn bài: COCI 2009-2010 contest 4