给定一个字符串 $$$S$$$,长度为 $$$n$$$,由数字组成 0–9。您想使用此字符串生成扫雷的变体。在此变体中,一个单元可能包含多个地雷,并且单元中的地雷计数基于其 4 邻域(边缘相邻单元),而不是通常的 8 邻域。
为此,您选择一个表示网格宽度的整数 $$$w$$$ ($$$1 \le w \le n$$$)。您将编号从 $$$0$$$ 到 $$$n-1$$$ 的 $$$n$$$ 单元格排列到网格中。网格的 $$$\left\lceil n / w \right\rceil$$$ 行从上到下编号为 $$$0$$$ 到 $$$\left\lceil n / w \right\rceil-1$$$,$$$w$$$ 列从左到右编号为 $$$0$$$ 到 $$$w-1$$$。对于每个 $$$0 \leq i \lt n$$$,单元格 $$$i$$$ 位于 $$$\left\lfloor i/w \right\rfloor$$$ 行和 $$$i \bmod w$$$ 列,并且对应于 $$$S$$$ 的第 $$$(i+1)$$$ 位。因此,行 $$$0$$$ 包含单元格 $$$0$$$ 到 $$$w-1$$$,行 $$$1$$$ 包含单元格 $$$w$$$ 到 $$$2w-1$$$,依此类推。请注意,最底行包含的单元格可能少于 $$$w$$$。
排列网格后,执行以下步骤:
- 对于对应于非零数字 $$$x$$$ 的每个单元格 (1–9),你在该单元格中放置了 $$$x$$$ 地雷。
- 对于每个剩余单元格对应 0,您在该单元格中写入一个数字,该数字等于其相邻单元格中的地雷总数。如果两个单元共享一条边,则它们是相邻的。注意每个单元格最多有 四 相邻单元格。
对于宽度 $$$w$$$,将 $$$f(w)$$$ 定义为生成的网格上没有地雷的所有单元格中的数字之和。给定一个整数 $$$k$$$,您的任务是计算值 $$$f(1)、f(2)、\ldots、f(n)$$$ 中的第 $$$k$$$ 个最大值。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\leq k \leq n \leq 500\,000$$$)。
第二行包含长度为 $$$n$$$ 的字符串 $$$S$$$,由数字组成 0–9.
输出
输出$$$f(1)、f(2)、\ldots、f(n)$$$中第$$$k$$$个最大值。
示例
输入复制
5 3 20103
输出复制
7
输入复制
5 1 20103
输出复制
11
输入复制
8 4 60409003
输出复制
35
注意
示例输入/输出#1 的说明
图 F.1 说明了宽度 $$$1$$$ 到 $$$5$$$ 的结果网格。单元格中的每个点代表一个地雷。
![]() |
| 图 F.1:所有 $$$5$$$ 可能宽度的网格结果。 |
通过对不含地雷的单元格上的数字进行求和,您将得到以下结果。
- $$$f(1) = 7$$$
- $$$f(2) = 3$$$
- $$$f(3) = 11$$$
- $$$f(4) = 4$$$
- $$$f(5) = 7$$$
其中第三大值是$$$7$$$。
