Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DTOGRADA - Sơn tường

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 ≤ 106) là số tấm ván cần phải sơn và số nguyên X (1 ≤ X ≤ 105).
  • Dòng tiếp theo ghi N số nguyên dương (mỗi số không quá 106) 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


Được gửi lên bởi:khanhptnk
Ngày:2010-02-15
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:COCI 2009-2010 contest 4

hide comments
2015-12-02 16:39:31 Thanga2pbc
RMQ+inline:v
2015-10-23 02:48:06 Le Minh Duc
trâu cũng qua :)))
2015-06-12 09:37:29 there's no salvation for me...
dequeue + mảng cộng dồn + IT + ứng dụng của heap và KMP =)))
2015-06-12 04:13:19 Tran Thuy Luc
KMP
2015-06-11 09:31:29 [Nghien] Le Long
Dijkstra Heap
2014-10-14 15:37:57 Vcoder_2014
ai co test nao post len minh voi
2011-12-27 01:20:55 Hoàng Hà
Time đã được chỉnh lại \m/
2010-03-09 12:34:22 Tran Manh Chanh Quan
Hu hu. Em gọi RMQ 2 lần là 2 O(N log x) thế mà vẫn không được sao trời :(( T_T

Last edit: 2010-03-09 13:12:33
2010-03-07 21:27:11 Tue Le
Time bài này chặt quá!
2010-02-26 18:04:21 Phạm Quang Vũ
Time limit kỳ quá T__T, máy SPOJ lởm hơn COCI mà. Cho thêm tầm 0.1~0.2 second đi em, ko dùng đúng cách thì vẫn TLE thôi mà :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.