[ROIR 2022] 礼物 (Day 2)

Luogu

IDLGP10093

Time1000ms

Memory128MB

DifficultyP6

2022Special Judge前缀和ST 表链表ROIR（俄罗斯）

帮助沃瓦选择 $l$ 和 $r$，使得 $1 \le l \le r \le n,r - l + 1 \ge k$，并且他得到的礼物的总快乐程度最大化（不包括给妹妹的礼物）。 ## Input 第一行输入两个整数 $n$ 和 $k$，表示放在沃瓦面前的礼物数量和需要给玛莎的礼物数量。第二行输入 $n$ 个整数，用空格分隔，第 $i$ 个数 $a_i$ 表示每个礼物带来的快乐程度。 ## Output 输出一个整数，表示沃瓦所选择的礼物的总快乐程度，不包括给玛莎的礼物。 [samples] ## Background 翻译自 [ROIR 2022 D2T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。圣诞老人让沃瓦选择一个礼物。在沃瓦面前有 $n$ 个礼物排成一行。每个礼物给沃瓦带来的快乐程度值用一个整数表示，第 $i$ 个礼物的值为 $a_i$。快乐程度可以是正数、负数或零。圣诞老人让沃瓦选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$。沃瓦需要选择从 $l$ 到 $r$ 之间的所有礼物。然而，在所选的礼物中，沃瓦必须把具有前 $k$ 大快乐程度值的 $k$ 个礼物给他的妹妹玛莎。 ## Note 在样例 $1$ 中，沃瓦不需要给玛莎任何礼物，因此他将选择 $l = 3, r = 5$，并且所选礼物的总快乐程度为 $5 + (−1) + 7 = 11$。在样例 $2$ 中，沃瓦将需要将带来最大快乐程度的礼物给玛莎。然后，他仍然会选择 $l = 3, r = 5$，但总共的快乐程度是 $5 + (−1) = 4$。在样例 $3$ 中，沃瓦需要给玛莎快乐值前二大的礼物。这种情况下，不难发现实际上沃瓦最好的选择方式是只选择两个礼物，然后全部给妹妹玛莎。一个最佳选择是选择 $l = 1, r = 2$。此时总快乐程度为 $0$。本题使用捆绑测试。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $7$ | $n\le200$ | | $2$ | $8$ | $n\le1000$ | | $3$ | $10$ | $n\le6000$ | | $4$ | $8$ | $k=0$ | | $5$ | $14$ | $k=1$ | | $6$ | $39$ | $n\le80000$ | | $7$ | $14$ | 无 | 对于 $100\%$ 的数据，$1 \le n \le 200000, 0 \le k \le \min(100, n),−10^9 \le a_i \le 10^9$。

Samples

Input #1

5 0
2 -4 5 -1 7

Output #1

Input #2

5 1
2 -4 5 -1 7

Output #2

Input #3

5 2
2 -4 5 -1 7

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2022] 礼物 (Day 2)",
    "description": {
      "content": "帮助沃瓦选择 $l$ 和 $r$，使得 $1 \\le l \\le r \\le n,r - l + 1 \\ge k$，并且他得到的礼物的总快乐程度最大化（不包括给妹妹的礼物）。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10093"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "帮助沃瓦选择 $l$ 和 $r$，使得 $1 \\le l \\le r \\le n,r - l + 1 \\ge k$，并且他得到的礼物的总快乐程度最大化（不包括给妹妹的礼物）。\n\n## Input\n\n第一行输入两个整数 $n$ 和 $k$，表示放在沃瓦面前的礼物数量和需要给玛莎的礼物数量。\n\n第二行输入 $n$ 个整数，用空格分隔，第 $i$ 个数 $a_i$ 表示每个礼物带来的快乐程度。\n\n## ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments