题意概述

我们有一个 $n \times n$ 的棋盘：

• 每个格子有颜色（1 红色 / 2 黄色）和分数 $f_{i,j}$（可以为负）。
• 左上角 $(1,1)$ 分数为 $0$。

三个机器人 $A,B,C$ 从 $(1,1)$ 出发，每步可以 向下或向右 跳跃。
初始跳跃距离为 $d$。
如果花费 $g$ 金币，跳跃距离可以变为 $[\max(1, d-g), d+g]$ 之间的整数。

跳跃规则：

1. 跳到格子得到该格子分数。
2. 如果跳之前和跳之后的格子颜色相同，额外获得 $1$ 分。
3. 可以在任意时刻结束游戏（不一定要到右下角）。
4. 三个机器人独立，路线可以相同。

最终得分：

$$S = A \times 20\% + B \times 30\% + C \times 50\%. $$

获得 $\lfloor S \rfloor$ RMB。

---

图书馆与读者部分

图书馆有 $m$ 本书，编码为 $c_i$。
有 $q$ 个读者，每人：

• 需求码长度 $l_i$
• 需求码 $b_i$（无前导 0）
• 如果借不到书，需要 $w_i$ RMB 说服

定义：一个读者被满足，当且仅当图书馆中有某本书 $c_j$ 的后 $l_i$ 位等于 $b_i$。

如果读者不被满足，就需要花费 $w_i$ RMB 去说服。
图书馆的总说服费用 = 所有不被满足的读者的 $w_i$ 之和。

---

目标

我们需要通过花费金币 $g$ 来调整机器人跳跃范围，从而让三个机器人可以走出足够高的得分，使得获得的 RMB $\ge$ 图书馆的总说服费用。
求最小的 $g$，如果无解输出 $-1$。

---

问题分解

第一步：计算图书馆的总说服费用

对于每个读者 $i$，检查是否有 $c_j \bmod 10^{l_i} = b_i$。
如果没有，则需要 $w_i$ RMB。
设总说服费用为 $W$。

我们需要 $\lfloor S \rfloor \ge W$。

---

第二步：计算三个机器人的最大总分 $S$

设 $A_{\max}(g)$ 表示在跳跃范围 $[\max(1, d-g), d+g]$ 下，机器人 $A$ 能获得的最大分数（可以随时结束）。
类似地 $B_{\max}(g)$ 和 $C_{\max}(g)$ 独立最大。

那么：

$$S_{\max}(g) = 0.2 \times A_{\max}(g) + 0.3 \times B_{\max}(g) + 0.5 \times C_{\max}(g). $$

因为三个机器人独立，且路线可以相同，所以它们可以各自选择自己的最优路径（不一定要相同），因此 $S_{\max}(g)$ 就是三者独立最大值的加权和。

所以我们要判断是否存在 $g$ 使得 $\lfloor S_{\max}(g) \rfloor \ge W$。

---

第三步：对单个机器人求最大得分

这是一个 带权最大路径 问题，但特殊点：

1. 跳跃距离是一个范围 $[L, R]$，其中 $L = \max(1, d-g), R = d+g$。
2. 每次只能向下或向右。
3. 路径可以随时结束（停在某个格子）。
4. 额外奖励：如果相邻两格子颜色相同，额外 $+1$。

设 $dp[i][j]$ 表示到达 $(i,j)$ 的最大得分（可以在 $(i,j)$ 结束）。

状态转移：

• 可以从 $(i-k, j)$ 向下跳 $k$ 步到达 $(i,j)$，其中 $L \le k \le R$ 且 $1 \le i-k \le n$。
• 可以从 $(i, j-k)$ 向右跳 $k$ 步到达 $(i,j)$，其中 $L \le k \le R$ 且 $1 \le j-k \le n$。
• 转移时加上 $f[i][j]$，并且如果颜色与上一步格子相同，额外 $+1$。

初始化 $dp[1][1] = 0$（因为 $f[1][1]=0$，且没有上一步）。

最终该机器人最大得分 = $\max_{1\le i,j\le n} dp[i][j]$（因为可以随时结束）。

---

第四步：复杂度与优化

直接 DP 复杂度 $O(n^3)$（因为每个点要从 $O(n)$ 个可能的前驱转移），$n$ 最大 $1000$ 会超时。

注意到跳跃范围 $[L,R]$ 长度是 $2g+1$，如果 $g$ 较小，那么转移来源是 $O(g)$ 的，不是 $O(n)$。

我们可以优化：
对于每个 $(i,j)$，需要检查：

• 从上方 $i-k$ 来：$k \in [L,R]$，且 $i-k \ge 1$。
• 从左方 $j-k$ 来：$k \in [L,R]$，且 $j-k \ge 1$。

因此我们可以维护一个 滑动窗口最大值 结构：

• 对每一列 $j$，维护从上到下的 $dp[i][j]$ 在窗口长度 $R-L+1$ 内的最大值。
• 对每一行 $i$，维护从左到右的 $dp[i][j]$ 在窗口长度 $R-L+1$ 内的最大值。

这样转移可以 $O(1)$ 得到最优前驱。

总复杂度 $O(n^2)$，可以接受。

---

第五步：搜索最小的 $g$

$g$ 范围：

• 下界 $0$（不花钱）。
• 上界：由于跳跃距离不能超过 $n$，$d+g \le n$ 且 $d-g \ge 1$，所以 $g \le n-1$。

我们可以在 $[0, n-1]$ 范围内 二分 $g$：

• 对每个 $g$ 计算 $A_{\max}(g), B_{\max}(g), C_{\max}(g)$。
• 计算 $S_{\max}(g)$，判断是否 $\lfloor S_{\max}(g) \rfloor \ge W$。

二分 $g$ 的可行性：

• 如果 $g$ 增大，跳跃范围 $[L,R]$ 变宽，可达的格子增多，得分不会减少（因为可以走原来的路径，或者走更优路径）。
  所以 $S_{\max}(g)$ 关于 $g$ 单调不减，可以二分。

---

第六步：无解判断

如果在 $g = n-1$（最大可能）时，$S_{\max}(g)$ 仍不足以 $\ge W$，则输出 $-1$。

---

算法步骤总结

1. 计算总说服费用 $W$
   对每个读者检查图书馆是否有匹配的书（用哈希或字典树后缀匹配），累加未满足读者的 $w_i$。

2. 二分 $g$
   下界 $0$，上界 $n-1$。

3. 对给定的 $g$

   • 计算 $L = \max(1, d-g)$, $R = d+g$。
   • 用滑动窗口 DP 计算 $A_{\max}(g), B_{\max}(g), C_{\max}(g)$（三者独立，但计算方法相同，可以只算一次最大得分，因为地图一样，只是机器人独立）。
   • 计算 $S_{\max}(g)$ 并判断是否 $\ge W$。

4. 输出最小 $g$ 或 $-1$。

---

样例解析

样例 1

$n=5, d=2$，计算得 $W=30$。
$g=0$ 时跳跃范围 $[2,2]$，可能无法得到足够高分。
$g=1$ 时跳跃范围 $[1,3]$，可以走出 $A=34, B=32, C=30$，$S=31.4 \ge 30$，所以 $g=1$ 可行。

样例 2

棋盘分数有很多负值，即使 $g$ 最大也无法达到 $W$，输出 $-1$。

---

复杂度分析

• 计算 $W$：$O(m + q \cdot \text{len})$，其中 $\text{len} \le 9$，可以 $O(1)$ 比较。
• 每个 $g$ 的 DP：$O(n^2)$，用滑动窗口。
• 二分 $g$：$O(\log n)$ 次检查。

总复杂度 $O(n^2 \log n)$，$n \le 1000$ 可过。

---

关键点

1. 图书馆部分只是用来计算说服费用 $W$，与棋盘无关。
2. 三个机器人独立，可以分别走最优路径，因此 $S_{\max}$ 是各自最大值的加权和。
3. 跳跃范围单调性 使得可以二分 $g$。
4. DP 优化 用滑动窗口维护列和行的最大值，将复杂度从 $O(n^3)$ 降为 $O(n^2)$。

这样就能高效求解。