取宝石

2025 全国青少年信息素养大赛 复赛 C++ · 初中组 第 10 题

题目描述

探险队进入了一个神秘地宫，里面有 n 堆宝石，每堆宝石个数为正整数。旁边有一面石碑，上面刻着取宝石的规则：探险者需要选定一堆宝石，从这堆宝石开始每隔 k-1 堆宝石拿一堆宝石（即每隔 k-1 堆取一堆，相邻两次所取宝石堆相隔 k）。

已知每一堆宝石的数量，请问探险队最多能拿走多少个宝石？

输入格式

第一行：两个正整数 n、k，用一个空格隔开。

第二行：n 个正整数 a₁, a₂, …, aₙ，表示每堆宝石的个数。

输出格式

一个整数，表示最多能拿走的宝石个数。

样例输入

7 3
4 6 2 1 10 1 3

样例输出

16

样例说明

• 从第 1 堆开始：拿第 1、4、7 堆 → 4+1+3 = 8
• 从第 2 堆开始：拿第 2、5 堆 → 6+10 = 16
• 从第 3 堆开始：拿第 3、6 堆 → 2+1 = 3
• 从第 4 堆开始：拿第 4、7 堆 → 1+3 = 4
• 从第 5 堆开始：拿第 5 堆 → 10
• 从第 6 堆开始：拿第 6 堆 → 1
• 从第 7 堆开始：拿第 7 堆 → 3

最大值为 16。

数据范围

• 对于 60% 的数据：1 ≤ n ≤ 10³，1 ≤ k ≤ n。
• 对于 100% 的数据：1 ≤ n ≤ 5×10⁵，1 ≤ k ≤ n，每堆宝石个数为不超过 10⁵ 的正整数。