시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB207282714.062%

문제

수학에는 정말 아름다운 기호가 많다. 수학나라의 수학왕은 특히 합, 곱, 절댓값을 좋아한다. 수학왕은 당신에게 다음의 문제를 냈다.

"길이 $N$인 정수로 이루어진 수열 $A$가 주어진다. 그 뒤, 서로 겹치지 않게 $K$개 이하의 구간을 잡는다. 이때, 각 구간의 길이는 $1$ 이상이어야 한다.

구간의 개수를 $X(\ge 1)$개 라고 할 때, 각 구간의 원소의 합을 $S_i (i = 1, 2, \cdots, X)$라 하자. 이때 $\left\vert S_1 S_2 \cdots S_X \right\vert$의 최댓값은 무엇인가?"

수학왕에게 인정받기 위해 문제를 해결하자!

입력

첫 번째 줄에 $N, K$가 주어진다.

이후 $N$줄에 걸쳐 $i + 1$번째 줄에 $A_i$가 주어진다.

출력

첫 번째 줄에 $K$개 이하의 구간을 잡았을 때의 최댓값을 출력한다.

제한

  • $1$ $\leq$ $N$ $\leq$ $100000$
  • $1$ $\leq$ $K$ $\leq$ $6$
  • $-10^9$ $\leq$ $A_i$ $\leq$ $10^9$
  • 답은 $10^{18}$을 넘지 않는다.

예제 입력 1

6 2
6
-5
5
5
5
5

예제 출력 1

120

$1$번 예제에서는 $(1), (3, 4, 5, 6)$으로 구간을 설정하면 $6 \times (5+5+5+5) = 120$이고, 이는 최댓값이다.

예제 입력 2

5 2
5
5
5
5
5

예제 출력 2

150

$2$번 예제에서는 $(1, 2), (3, 4, 5)$으로 구간을 설정하면 $(5+5) \times (5+5+5) = 150$이고, 이는 최댓값이다.

출처

High School > 경기과학고등학교 > 나는코더다 2022 송년대회 C번