問題一覧 > 通常問題

No.1117 数列分割

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : ir_1st_vilir_1st_vil / テスター : shinchanshinchan
10 ProblemId : 4450 / 出題時の順位表
問題文最終更新日: 2020-07-08 00:28:20

注意

この問題は実行時間制限が厳しいので高速な言語を使用することを勧めます。(writer解はPython3ではTLE、PyPy3ではACすることを確認しています。)

問題文

長さ$N$の数列$A$があります。この数列を以下の条件を満たすように$K$個の連続部分列$B_1,B_2,\dots,B_K$に分割することを考えます。

  • $B_1,B_2,\dots,B_K$はいずれも$A$の空でない長さ$M$以下の連続部分列である。
  • $B_1,B_2,\dots,B_K$をこの順序で連結すると$A$となる。

ある分割のスコアは$\sum_{i=1}^{K}|\sum_{j=1}^{L_i}B_{ij}|$と定義されます。ここで$L_i$は$B_i$の長さです。

スコアの最大値を求めてください。

入力

$N\ K\ M$
$A_1\ A_2\ \dots\ A_n$

  • 入力は全て整数
  • $1 \le N \le 3000$
  • $1 \le K,M \le N$
  • $N \le M \times K$
  • $|A_i| \le 10^9$

出力

スコアの最大値を出力し、最後に改行してください。

サンプル

サンプル1
入力
5 2 4
-7 -7 17 3 -20
出力
26

例えば$[-7,-7],[17,3,-20]$と分割した場合のスコアは、$|-7-7|+|17+3-20|=|-14|+|0|=14+0=14$となります。

ここでは$[-7,-7,17,3],[-20]$という分割が最適で、スコアの最大値は$26$となります。

サンプル2
入力
3 2 2
-6 -15 13
出力
34
サンプル3
入力
9 5 3
17 11 9 -10 -20 5 19 -3 -3
出力
97

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。