문제
준석이는 정글히트 게임(-도시를 키우고 적을 공격하는 스마트폰 게임)을 아주 좋아합니다. 그는 게임 안에서 일렬로 N개의 건물을 지었습니다. 이 건물들은 각각의 높이가 있습니다.
하지만 건물을 지었다는 기쁨도 잠시, 건물을 짓느라 무리한 준석이는 자금난에 허덕이다가 결국 건물들을 그의 친구인 형준이에게 팔 수밖에 없는 상황에 놓였습니다. 형준이는 준석이의 건물 중 K개 이상으로 이루어진 연속된 구간을 잡아 이를 사려고 합니다.
준석이는 건물을 팔면서, 그 건물들의 (최대 높이) * (최소 높이)만큼의 돈을 받기로 했습니다. 건물의 개수와는 상관없이 말이죠.
준석이는 이 (K개 이상의 연속된)건물들을 팔아 최대한의 돈을 얻고자 합니다. 준석이가 얻을 수 있는 최대한의 돈을 알려 주세요! 건물의 개수는 상관이 없습니다.
입력
첫째 줄에 준석이가 지은 건물의 수인 N과, 준석이가 잡을 구간의 최소 길이인 K가 주어집니다.
둘째 줄에는 N개의 수가 공백을 사이에 두고 주어집니다. 이는 차례대로 준석이가 지은 건물의 높이입니다.
모든 건물의 높이는 1,000이하의 양의 정수입니다.
<제약조건>
서브태스크 1 : N≤100. 1≤K≤N. 전체 데이터의 28%
서브태스크 2 : N≤2,000. 1≤K≤N. 전체 데이터의 56%
서브태스크 3 : N≤100,000. 1≤K≤N.
출력
준석이가 얻을 수 있는 돈의 최댓값을 출력합니다.
예제 #1
10 4
9 7 7 7 8 2 2 2 2 10
63
준석이가 [9,7,7,7,8]의 구간을 잡으면 준석이가 받는 돈, 즉 (구간 중 최소 높이) * (구간 중 최대 높이)는 9*7로 63이 됩니다.
예제 #2
10 6
9 7 7 7 8 2 2 2 2 10
20
로그인해야 코드를 작성할 수 있어요.