生日礼物

Luogu

IDLGP10478

Time1000ms

Memory512MB

DifficultyP5

贪心优先队列反悔贪心

ftiasch 18 岁生日的时候，lqp18_31 给她看了一个神奇的序列 $A _ 1$, $A _ 2$, ..., $A _ N$。她被允许选择不超过 $M$ 个连续的部分作为自己的生日礼物。自然地，ftiasch 想要知道选择元素之和的最大值。你能帮助她吗? ## Input 第 1 行，两个整数 $N$ ($1 \le N \le 10 ^ {5}$ ) 和 $M$ ($0 \le M \le 10 ^ 5$)，表示序列的长度和可以选择的部分。第 2 行， $N$ 个整数 $A_1$, $A_2$, ..., $A_N$ ($0 \le \mid A_i\mid \le 10^4$)，表示序列。 ## Output 一个整数，表示最大的和。 [samples]

Samples

Input #1

5 2
2 1 -2 3 -2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "生日礼物",
    "description": {
      "content": "ftiasch 18 岁生日的时候，lqp18_31 给她看了一个神奇的序列 $A _ 1$, $A _ 2$, ..., $A _ N$。 她被允许选择不超过 $M$ 个连续的部分作为自己的生日礼物。 自然地，ftiasch 想要知道选择元素之和的最大值。你能帮助她吗?",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10478"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "ftiasch 18 岁生日的时候，lqp18_31 给她看了一个神奇的序列 $A _ 1$, $A _ 2$, ..., $A _ N$。 她被允许选择不超过 $M$ 个连续的部分作为自己的生日礼物。\n\n自然地，ftiasch 想要知道选择元素之和的最大值。你能帮助她吗?\n\n## Input\n\n第 1 行，两个整数 $N$ ($1 \\le  N \\le 10 ^ {5}$ ) 和 $M$ ($0...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments