[BalticOI 2022] Uplifting Excursion (Day1)

Luogu

IDLGP8392

Time1000ms

Memory128MB

DifficultyP6

动态规划 DP贪心2022BalticOI（波罗的海）

有 $2m+1$ 种物品，重量分别为 $-m,-m+1,\ldots, m-1,m$。重量为 $i$ 的物品有 $a_i$ 个。你需要拿走若干物品，使得这些物品重量之和恰好为 $l$。在此基础上，你需要拿尽可能多的物品。问在物品重量之和恰好为 $l$ 的基础上，你最多能拿多少物品。 ## Input 第一行两个数 $m,l$。第二行 $2m+1$ 个数，分别为 $a_{-m},a_{-m+1},\ldots, a_{m-1},a_m$。 ## Output 一行一个数表示答案。若不存在方案，输出 `impossible`。 [samples] ## Note 子任务 $1$ ($5$ 分)：$m , a_i≤50$ 子任务 $2$ ($15$ 分)：$m , a_i≤100$。子任务 $3$ ($20$ 分)：$m≤30$。子任务 $4$ ($20$ 分)：$m ≤50$。子任务 $5$ ($20$ 分)：$m ≤ 100$。子任务 $6$ ($20$ 分)：没有特殊限制。对于子任务 $3$ 到子任务 $6$，如果通过 $\forall i<0,a_i=0$ 的测试点，可以获得一半的得分。对于所有数据，满足 $1\leq m \leq 300$，$-10^{18}\le l \le 10^{18}$，$0\le a_i\le 10^{12}$。

Samples

Input #1

2 5
2 3 1 1 4

Output #1

Input #2

3 5
3 1 0 2 0 0 2

Output #2

impossible

API Response (JSON)

{
  "problem": {
    "name": "[BalticOI 2022] Uplifting Excursion (Day1)",
    "description": {
      "content": "有 $2m+1$ 种物品，重量分别为 $-m,-m+1,\\ldots, m-1,m$。重量为 $i$ 的物品有 $a_i$ 个。 你需要拿走若干物品，使得这些物品重量之和恰好为 $l$。在此基础上，你需要拿尽可能多的物品。 问在物品重量之和恰好为 $l$ 的基础上，你最多能拿多少物品。",
      "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": "LGP8392"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $2m+1$ 种物品，重量分别为 $-m,-m+1,\\ldots, m-1,m$。重量为 $i$ 的物品有 $a_i$ 个。\n\n你需要拿走若干物品，使得这些物品重量之和恰好为 $l$。在此基础上，你需要拿尽可能多的物品。\n\n问在物品重量之和恰好为 $l$ 的基础上，你最多能拿多少物品。\n\n## Input\n\n第一行两个数 $m,l$。\n\n第二行 $2m+1$ 个数，分别为 $a_{-m},a_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments