← 返回题目列表

AtCoder · abc383_g

G. 酒吧盖

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

分数: 625 点

问题陈述

你有一排 N 细胞。的 i左侧第一个单元格包含一个整数 A_i.

你还有 \lfloor \frac{N}{K} \rfloor 瓷砖,每个瓷砖覆盖 K 连续单元格。

对于每个 i = 1, \ldots, \lfloor \frac{N}{K} \rfloor,解决以下问题:

  • 准确放置时 i 没有重叠的图块,找到所覆盖单元格中数字的最大可能总和。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq \min(5,N)
  • -10^9 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 \ldots A_N

输出

打印以下问题的答案 i = 1, \ldots, \lfloor \frac{N}{K} \rfloor 一行中以空格分隔。


示例输入 1

6 2
-5 3 4 -1 6 -2

示例输出 1

7 12 5

对于 i=1,如果用一块图块覆盖第二个和第三个单元格,则被覆盖单元格中的数字之和为 7.

对于 i=2,如果用一块瓷砖覆盖第 2 和第 3 个单元格,用另一块瓷砖覆盖第 4 和第 5 个单元格,则覆盖的单元格中的数字之和为 12.


示例输入 2

20 4
-5 3 4 -1 6 -2 13 -1 13 7 6 -12 3 -5 12 -6 -3 10 -15 -5

示例输出 2

32 45 57 52 22