루미 알고리즘

#1565골드Fence Building

PO 2023 온라인 예선코딩출제 Erik Hedin, Victor Vatn영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Gustav loves his neighbors and has therefore built a fence consisting of N boards. The boards are all 1 dm wide, but can be of different heights.

To help the neighborhood flourish, Gustav now wants to hang a rectangular notice board on this fence. Gustav feels that the notice board he hangs up must be perfect and therefore needs your help!

Specifically, Gustav wants the notice board to be as large as possible (i.e., have the largest possible area). The notice board also needs to hang securely, which means that there can be at most K boards behind the notice board that do not reach all the way up to its upper edge. For the notice board to hang at all, it must, of course, have at least one board behind it that reaches all the way up to its upper edge.

Input

The first line contains two integers N (1 ≤ N ≤ 50000) and K (0 ≤ K ≤ 20), the number of boards that make up the fence and the number of boards that can be missing behind the notice board.

The second line contains N integers h_1, h_2, …, h_N (1 ≤ h_i ≤ 10^9) where h_i is the height of the i-th board from the left in decimeters.

Output

Print an integer: the largest possilbe area of a rectangular notice board, in dm^2.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
19N ≤ 100, K = 1
222h_1 < h_2 < … < h_N
325K = 0
416N ≤ 2000
528No additional constraints.

Explanation of samples

In the first sample, no board behind the notice board can be below the upper edge of the board. By putting up a board with a height of 4 dm in front of the three middle boards, the board will have an area of 12 dm^2, which is the best largest possible board.

In the second sample, Gustav's best option is to put up a board along the entire fence with a height of 4 dm. The boards with heights of 1 dm and 2 dm are indeed below the upper edge of the notice board, but this is acceptable since K = 2.

In the third example, it does not matter how many boards are below the upper edge of the notice board. Instead, the requirement that the board must have at least one board behind it that reaches all the way up comes into play, so its height still cannot exceed 9 dm.

예제

예제 1

입력
7 0
6 2 5 4 5 1 6
출력
12

예제 2

입력
7 2
6 2 5 4 5 1 6
출력
28

예제 3

입력
6 6
9 1 6 2 3 5
출력
54

출처 표기

출처: Programmeringsolympiaden 2023년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.