프로그램 명: coci_ograd
제한시간: 1 초
Matija는 오래된 울타리를 색칠해야 합니다. 이 울타리는 너비가 1cm, 높이가 여러 가지인 널빤지 N개로 만들어졌습니다. 이 작업을 빨리 하기 위해, 그는 "Super Paint Roller Deluxe"를 구매했습니다. 이 롤러의 폭은 X cm입니다. Matija는 페인트질을 할 때 롤러의 모든 부분을 널빤지 위에 둬야 합니다. (페인트가 흘러서 주위를 얼룩지게 할 수 있기 때문입니다.) 또한, 페인트질 중에 롤러는 언제나 땅과 평행해야 합니다. 즉, Matija가 롤러를 안전하게 쓰기 위해서는, 그는 X개의 연속된 널빤지를 선택해서, 맨 밑에서부터 X개의 널빤지 중 가장 높이가 낮은 널빤지 전체를 색칠할 때까지 한 번에 색칠해야 합니다. 그 다음 그는 다른 X개의 널빤지를 선택해서, 같은 방법으로 칠하는 작업을 반복합니다.
이렇게 색칠하면 널빤지의 몇 부분이 색칠되지 않기 때문에, Matija는 그 부분을 칫솔로 색칠해야 합니다. 이것은 누구나 알다시피 꽤 지루한 작업이기 때문에, Matija는 여러분에게 Super Paint Roller Deluxe를 이용해서 가장 많은 영역을 색칠할 수 있도록 도와 달라고 요청했습니다. 이러한 방법이 여러 개 있다면, 그는 최소한의 롤러질 횟수로 색칠할 수 있기를 원합니다.
입력
-
첫 번째 줄에 널빤지의 수 N (1 ≤ N ≤ 1 000 000), Super Paint Roller Deluxe의 너비 X (1 ≤ X ≤ N ≤ 100 000)가 주어집니다.
-
두 번째 줄에 널빤지들의 높이를 의미하는 1 000 000 이하의 자연수 N개가 주어집니다.
출력
-
첫 번째 줄에 Matija가 칫솔로 칠해야 할 최소한의 널빤지의 영역을 출력합니다.
-
두 번째 줄에 이 때 필요한 최소한의 롤러질 횟수(?)를 출력합니다.
Matija needs to paint his old fence. The fence is made from N planks, each 1 cm in
width and varying in height. To do this easy and fast, he bought himself a Super Paint
Roller Deluxe. The paint roller is X cm wide. The Super Paint Roller Deluxe model
comes with a catch, however. Matija must at all times touch the planks with full
width of the roller, otherwise paint drops all around and stains everything. Also, the
roller must always be parallel to the ground to prevent leakage. This means that in
order for Matija to use the roller safely, he needs to select X planks, and paint them
from bottom to the top of the lowest plank in one swoop. Then he selects some other
X planks, paints them and so on.
This leaves parts of some planks unpainted. Matija will have to paint such parts with a
toothbrush. This is obviously quite tedious so he asked you to help him paint as much
as possible using the Super Paint Roller Deluxe. Since there is more than one way
to do this he is also interested in the painting that requires the minimal number of
swoops.
입력
-
The first line of input contains two integers N (1 ≤ N ≤ 1 000 000), number of planks,
and X (1 ≤ X ≤ 100 000), width of the Super Paint Roller. Width of the Super Paint
Roller will not exceed the width of the fence.
-
The second line of input contains N positive integers, smaller than 1 000 000, heights
of planks in the fence.
출력
-
The first line of output should contain the smallest possible area Matija will have to
paint manually.
-
The second line of output should contain the smallest number of swoops needed.
SCORING
If only one of the output numbers is correct, you will receive 50% of points for that
test case. You must always follow the output format to the letter, even if you do
not calculate both numbers. In such case, you may output any integer in place of the
number you did not calculate.
입출력 예
입력
5 3
5 3 4 4 5
출력
3
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
sample description:
Matija needs two swoops with his roller - one to paint
planks 1, 2 and 3 to the height of 3 cm, the other to
paint planks 3, 4 and 5 to the height of 4 cm. Note
that 3 cm^2 (2 cm^2 on plank 1 and 1 cm^2 on plank 5)
are left unpainted. Also, 3 cm^2 on plank 3 are painted over twice, but that's OK.
출처:coci 2009-2010 contest4 4/6
번역:tncks0121
[질/답]
[제출 현황]
[푼 후(0)]