思路：
起首发现单调性，灵活性增加 \(x+1\) 的答案肯定不会比增加 \(x\) 的答案更劣。
那么可以二分求 \(g\)，则机器人每次可以移动 \([\max(d-mid,1),d+mid]\) 这个区间内的距离，为了方便，设为 \([l,r]\)。
考虑动态规划求得能走到的最大分数，令 \(dp_i\) 表示走到第 \(i\) 个格子的最大分数，则状态转移方程为：
\[dp_i = s_i + \max\limits_{j=0}^{i-1} [x_i - r \le x_j] [x_j \le x_i - l] dp_j\]
可以使用单调队列维护：
- 若当前队尾为 \(j\)，且 \(x_j < x_i - r\)，则这个 \(j\) 无法对 \(dp_i\) 造成贡献，直接不断弹出即可。
- 若当前队头为 \(j\)，且 \(x_{j+1} \le x_i - l\)，则这个 \(j+1\) 可以对 \(dp_i\) 造成贡献，不断插入即可。
- 因为要维护最大值，可以使用单调队列。
时间复杂度为 \(O(N \log W)\)。
完整代码：
[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod) x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=5e5+10;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c |
