시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1109 | 217 | 165 | 27.363% |
홍준이는 오래된 울타리를 색칠해야한다. 이 울타리는 너비가 1cm이고 높이가 여러 가지인 널빤지 N개로 만들어졌다. 색칠을 빨리 하기 위해, 홍준이는 롤러 Super Paint Roller Deluxe를 샀다. 이 롤러의 폭은 X cm이다. 홍준이는 색칠을 할 때, 롤러의 모든 부분이 널빤지를 벗어나지않게 해야한다. 그렇지 않으면 페인트가 흘러서 주위를 얼룩지게 할 수 있다. 또한, 색칠 중에 롤러는 언제나 땅과 평행해야한다. 즉, 홍준이가 롤러를 안전하게 쓰기 위해서는, X개의 연속된 널빤지를 선택해서 맨 밑에서부터 X개의 널빤지 중 가장 높이가 낮은 널빤지 전체를 색칠할 때까지, 한 번에 색칠해야한다. 그 다음 다른 X개의 널빤지를 선택해서, 같은 방법으로 칠하는 작업을 반복한다.
이렇게 색칠하면 널빤지의 몇 부분이 색칠되지 않으므로, 홍준이는 그 부분을 칫솔로 페인트칠 해야한다. 이건 누구나 알다시피 지루한 작업이기 때문에, 홍준이는 여러분에게 Super Paint Roller Deluxe를 이용해서 가장 많은 영역을 색칠할 수 있도록 도움을 요청했다. 이러한 방법이 여러 가지 있다면, 홍준이는 최소한의 롤러질 횟수로 색칠하려고한다. 홍준이를 도와, 칫솔로 칠해야 할 널빤지의 최소 넓이와 최소 롤러질 횟수를 구하는 프로그램을 작성하시오.
첫 번째 줄에 널빤지의 수 N (1 ≤ N ≤ 1 000 000), Super Paint Roller Deluxe의 너비 X (1 ≤ X ≤ 100 000, X ≤ N)가 주어진다.
두 번째 줄에 널빤지들의 높이를 의미하는 1 000 000 이하의 자연수 N개가 주어진다.
첫 번째 줄에 홍준이가 칫솔로 칠해야하는 널빤지 넓이의 최솟값을 출력한다.
두 번째 줄에 이때 필요한 최소한의 롤러질 횟수를 출력한다.
5 3 5 3 4 4 5
3 2
홍준이는 두 번의 롤러질을 한다. - 1, 2, 3번째 널빤지에 높이 3cm로, 나머지 3, 4, 5번째 널빤지에는 높이 4cm로 칠한다. 3cm²(2cm²는 1번 널빤지, 1cm²는 5번 널빤지)가 칠해지지 않아서 칫솔로 칠해야한다. 그리고 가운데 3번째 널빤지에 3cm²이 2번 중복되어서 칠해졌지만, 상관없다.
10 3 3 3 3 3 3 3 3 3 3 3
0 4
7 4 1 2 3 4 3 2 1
4 4