logo AlgoBeat OnlineJudge
登录 注册

#215626. [ROIR 2015 Day 1] prizes 奖品选择

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

阿丽莎和鲍勃成为了电视竞猜的获胜者,他们现在要选择奖品。共有 个奖品,编号从

奖品分配规则如下: 组织者给出一个正整数 )。首先,阿丽莎选择 个连续的奖品编号。然后,鲍勃选择 个连续的奖品编号,但不能选择阿丽莎已经选中的编号。之后,获胜者们领取他们选择的奖品。

阿丽莎非常了解鲍勃,并且她知道每个奖品对鲍勃的价值是多少(这是一个正整数)。阿丽莎不喜欢鲍勃,她希望选择奖品时,使得鲍勃选择的奖品总价值尽可能小。阿丽莎不关心自己得到哪些奖品。

任务:编写程序,根据奖品的价值和 的值,确定阿丽莎能做到的最小总价值 ,使得鲍勃选择的奖品总价值不会超过

输入格式

输入文件的第一行包含两个整数: —— 奖品总数, —— 每个获胜者必须选择的连续奖品数()。

第二行包含 个整数:,表示每个奖品对鲍勃的价值()。

输出格式

输出文件应包含一个整数 —— 最小的 ,使得阿丽莎能够让鲍勃选择的奖品总价值不超过

样例

样例输入 1

10 2
1 2 4 5 2 4 2 2 1 6

样例输出 1

7

数据范围与提示

示例说明

在这个示例中,阿丽莎可以选择第 和第 个奖品。此时,鲍勃可以选择第 和第 个奖品,获得的总价值为

任务评价系统与子任务说明

子任务 1(30分)

子任务 2(30分)

子任务 3(40分)

翻译来源:GPT 5.2。