题目详情题解（0）讨论（0）提交记录（0）

AT_past20_e.リンゴ集め

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有若干苹果掉落在数轴上。对于每个 i=1,2,…,Ni=1,2,\ldots,N，在坐标 ii 上会掉落 AiA_i 个苹果；其他坐标不会有苹果掉落。

你有一个宽度为 WW 的篮子。你可以自由选择整数 LL，将篮子的左端放在 LL 处，这样它就能收集掉落在 LL 到 L+W−1L+W-1（包含两端）这些坐标上的苹果。

你最多能收集到多少个苹果？

输入格式

输入从标准输入读入，格式如下：

N W A1 A2 … ANN\ W\ A_1\ A_2\ \ldots\ A_N

输出格式

输出答案。

输入输出样例

  • 输入#1

    5 3
3 1 4 1 5

    输出#1

    10

  • 输入#2

    10 10
1 1 1 1 1 1 1 1 1 1

    输出#2

    10

  • 输入#3

    12 4
314 159 265 358 979 323 846 264 338 327 950 288

    输出#3

    2506

说明/提示

样例解释 1

如果你选择 L=3L=3，那么篮子可以收集到掉落在 3,4,53,4,5 这三个坐标上的 4+1+5=104+1+5=10 个苹果。这是最多的情况。

数据范围

  • 1≤W≤N≤1061 \leq W \leq N \leq 10^6
  • 0≤Ai≤1030 \leq A_i \leq 10^3
  • 所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页