{"problem":{"name":"[BCSP-X 2024 12 月小学高年级组] 打怪升级","description":{"content":"Alice 在玩一个游戏，游戏共有 $n$ 个关卡，你需要操作 $1$ 个主角过关，主角有 $2$ 个属性： 1. 血量 2. 等级 每关的 Boss 会对主角造成伤害（血量减小），第 $i$ 关的 Boss 对等级为 $j$ 的主角造成的伤害值为 $b[i][j]$。 每关打完 Boss 后，在进入下一关前会得到一本经验书，你有 $2$ 个选择： 1. 回血：第 $i$ 关的经验书可以使","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4159"},"statements":[{"statement_type":"Markdown","content":"Alice 在玩一个游戏，游戏共有 $n$ 个关卡，你需要操作 $1$ 个主角过关，主角有 $2$ 个属性：\n\n1. 血量\n2. 等级\n\n每关的 Boss 会对主角造成伤害（血量减小），第 $i$ 关的 Boss 对等级为 $j$ 的主角造成的伤害值为 $b[i][j]$。\n\n每关打完 Boss 后，在进入下一关前会得到一本经验书，你有 $2$ 个选择：\n\n1. 回血：第 $i$ 关的经验书可以使血量增加 $a[i]$。\n2. 改变等级：若假设主角当前等级为 now，使用经验书可以将等级变为 $[1, now + 1]$ 中的任意值。\n\n你需要在 $2$ 个选择中择一执行。\n\n已知主角的初始血量为 $m$，初始等级为 $1$，游戏过程中任意时刻血量必须 $>0$。\n\n现在请问，在通过第 $k$ 个关卡之后（可以使用第 $k$ 关的经验书），主角能达到的最大等级是多少？如果无法通过第 $k$ 关，答案为 0。\n\n请你输出 $k = 1 \\sim n$ 的所有答案，注意这 $n$ 个询问是独立的。\n\n例如 $n = 3, m = 2, a = [2, 1, 1]$\n\n$$b[1][1] = 1$$\n$$b[2][1] = 2, b[2][2] = 3$$\n$$b[3][1] = 3, b[3][2] = 3, b[3][3] = 3$$\n\n- 当 $k = 1$ 时，第一关血量先减为 $2 - 1 = 1$，然后选择升为 2 级，答案为 $2$。\n- 当 $k = 2$ 时，第一关血量先减为 $2 - 1 = 1$，然后选择加血 $1 + 2 = 3$；第二关血量减为 $3 - 2 = 1$，然后选择升为 $2$ 级，答案为 $2$。\n- 当 $k = 3$ 时，无论如何选择都无法通过第 3 关，答案为 $0$。\n\n## Input\n\n第一行 $2$ 个整数 $n, m$，代表关卡数量和初始血量。\n\n第二行 $n$ 个整数 $a[1 \\sim n]$ 代表每关经验书的加血量。\n\n接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数代表第 $i$ 关的 Boss 对等级为 $1 \\sim i$ 的主角造成的伤害值。\n\n## Output\n\n输出 $n$ 行，第 $i$ 行包含 $1$ 个整数代表通过第 $i$ 个关卡之后，主角能达到的最大等级。\n\n[samples]\n\n## Note\n\n### 样例 3-5\n\n见附件。\n\n### 数据范围\n\n对于所有数据，$1 \\leq n \\leq 1500, 0 \\leq a[i], b[i][j] \\leq 100, 1 \\leq m \\leq 1500$\n\n本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。\n\n| 子任务编号 | 分值 | $n$ | 子任务依赖 |\n|:----------:|:----:|:-------:|:------------:|\n| 1          | 39   | $\\leq 10$ |            |\n| 2          | 43   | $\\leq 100$ | 1          |\n| 3          | 18   | $\\leq 1500$ | 1,2        |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4159","tags":["动态规划 DP","2024","北京","BCSP-X"],"sample_group":[["3 2\n2 1 1\n1\n2 3\n3 3 3","2\n2\n0"],["10 98\n67 100 76 15 44 86 38 95 5 8\n43\n25 91\n14 18 24\n79 79 60 85\n35 47 59 22 96\n53 78 43 95 55 25\n74 26 97 30 42 14 6\n100 70 79 49 83 74 43 38\n64 38 75 79 59 10 54 17 2\n34 19 19 4 23 90 99 97 93 10","2\n2\n3\n4\n4\n4\n5\n5\n5\n6"]],"created_at":"2026-03-03 11:09:25"}}