정올나라 최고의 파티쉐가 되고 싶은 한글이는 디저트 경연대회에서 다음 미션을 받았다.
폭이 모두 1이고, 밑변이 같은 높이에 놓인 레이디핑거 빵이 왼쪽에서 오른쪽으로 N개 일렬로 놓여 있다. 레이디핑거는 티라미수에 쓰이는 길쭉한 스펀지 비스킷으로, 이미 커피 시럽에 적셔져 있어 순서를 바꾸거나 기울여 자를 수 없다. 각 빵의 높이는 정수 h_1, h_2, \dots, h_N이다.

한글이는 이 빵들 중 연속된 구간 하나를 골라, 그 구간 전체를 같은 높이로 수평 절단하여 직사각형 모양의 티라미수 단면을 만들 수 있다. (빵을 대각선으로 자르는 것은 금지다.)

한글이는 티라미수를 직사각형 모양으로 만들고 싶기에, 이때 만들 수 있는 티라미수의 넓이는 (잘라낸 높이) \times (선택한 빵의 개수)이며, 잘라낸 높이는 선택한 구간의 모든 빵 높이보다 클 수 없다(= 구간의 최솟값 높이까지 가능).

만들 수 있는 티라미수 중 넓이의 최댓값을 구하라.

#8614 upload 91 done 35 how_to_reg 29 call_split Subtask

초거대 티라미수 만들기 timer 1s memory 1024MB

#8614
Subtask

초거대 티라미수 만들기 1s 1024MB