← 返回题目列表

AtCoder · awc0077_b

B. 糖果拼盘

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥在一家糖果店工作。店里有 N 糖果从左到右排成一排, i左边第一个糖果 (1 \leq i \leq N)的“美味”值为 A_i.

高桥现在将准确地做出 M 分类套装。每组糖果都是通过从一排糖果中选择一个连续的间隔来构建的。具体来说,他选择一对整数 (l, r) (1 \leq l \leq r \leq N)并将编号为的糖果捆绑在一起 l, l+1, \ldots, r。然而,长度 每个间隔的 r - l + 1 最多必须 K.

制作时 M 套,全部 M 选择的间隔必须不同。也就是说,对于任意两个集合,它们对应的对 (l, r) 不得相同。另一方面,不同组的间隔允许重叠,这意味着相同的糖果可以包含在多个组中。

每组的“满意度”被定义为该组中包含的糖果的美味值的总和。即,满足区间的集合 (l, r) is A_l + A_{l+1} + \cdots + A_r.

在所有方法中准确地制作 M 设置、查找并输出最大可能的总满意度 M 设置。

保证区间总数 (l, r) 长度最多 K 至少 M,所以总是可以选择 M 满足条件的不同区间。

约束

  • 1 \leq N \leq 3000
  • 1 \leq K \leq N
  • 1 \leq M \leq \displaystyle\sum_{k=1}^{K} (N - k + 1) (右侧等于长度最大的区间总数 K)
  • -10^6 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N M K
A_1 A_2 \ldots A_N
  • 第一行包含整数 N 代表糖果数量,整数 M 代表要制作的组数,整数 K 代表一组糖果的数量上限,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每种糖果的美味,以空格分隔。

输出

输出最大可能的总满意度 M 设置在一行中。


示例输入 1

5 3 2
3 -1 4 1 5

示例输出 1

16

示例输入 2

7 5 3
2 -3 5 -1 8 -2 4

示例输出 2

43

示例输入 3

10 4 4
1 -2 3 4 -5 6 7 -8 9 1

示例输出 3

49