시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 207 | 28 | 27 | 14.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$개 이하의 구간을 잡았을 때의 최댓값을 출력한다.
6 2 6 -5 5 5 5 5
120
$1$번 예제에서는 $(1), (3, 4, 5, 6)$으로 구간을 설정하면 $6 \times (5+5+5+5) = 120$이고, 이는 최댓값이다.
5 2 5 5 5 5 5
150
$2$번 예제에서는 $(1, 2), (3, 4, 5)$으로 구간을 설정하면 $(5+5) \times (5+5+5) = 150$이고, 이는 최댓값이다.
High School > 경기과학고등학교 > 나는코더다 2022 송년대회 C번