思考最朴素做法
\(f_{i,j,p}\)表示在第\(i\)个时刻终点为\(j\)且机器人走了\(p\)步获得的最大金币数，则有：
其中，\(r_{i,j}\)表示第\(i\)条路第\(j\)个时刻的金币，\(G_i\)表示在\(i\)个工厂买机器人的金币
初始化:\(\sum\limits_{i=1}^n f_{0,i,0}=G_i\)
我们发现可以降维，第三维其实可以用前缀和维护。
用\(f_{i,j}\)表示在第\(i\)个时刻走完后在工厂\(j\)买了机器的最大金币数
定义\(sum_{i,j}\)表示终点为\(i\)且走了\(j\)个时刻的金币
有\(sum_{i,j}=sum_{w(i-1),j-1}+r_{w(i-1),j}\)
定义函数\(val(st,la,ti)=sum_{w(st+ti),la+ti}-sum_{st,la}\)表示在第\(st\)个时刻第\(la\)个工厂开始走走了\(ti\)个时刻在道路上获得的金币，则有
时间复杂度\(O(n^3)\)需要优化
考虑单调队列
该单调区间内记录\(gs,ks,pos\)，其中\(gs\)表示买上一个机器人时获得的最大金币数为\(gs\)（注意，记录的是买了后的最大金币数），\(ks\)表示上一个机器人在第\(ks\)个工厂买，\(pos\)表示在第\(pos\)个时刻买
求答案时取队首的\(q\)，则\(ans=q_{gs}+val(q_{ks},q_{pos},i-q_{pos})\)
然而单调队列要满足一个性质无论何时都要满足单调性，所以我们发现不可以把所有的数都放到同一个单调队列，因为不同道路上的金币不同的时刻可能不同，若我们把他们放到同一个单调队列，可能会导致在第一个时刻从工厂一开始会更优，第二个时刻的时候从工厂二开始会更优（只有从第三个工厂到第四个工厂的道路在第二个时刻的金币足够多，而其他的道路的金币又足够少）。相信丧心病狂的出题人会构造的。
那么我们可以构造多个单调队列，单调队列\(q_i\)维护所有假设这个机器人一直在走，那么第0个时刻在i的数，这样他们第\(k\)个时刻必定会走同一条道路。因为他在\(pos\)时刻开始走，所以当\(i-pos>p\)或者有更优解时把它踢出队列。
最后再在取每一个单调队列的队首计算答案取\(max\)即可
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1010,INF=1e16;
ll n,m,p,tzy,ans=-INF;
ll r[N][N],G[N];
ll sum[N][N],f[N][N];
ll w(ll wz){return ((wz%n+n)%n)==0?n:((wz%n+n)%n);}
ll val(ll st,ll la,ll ti){return sum[w(st+ti)][la+ti]-sum[st][la];}
ll head[N],tail[N];
struct jgt{ll gs,ks,pos;}q[N][N];
void init()
{
for(ll i=1;i<=m;i++)
for(ll j=1;j<=n;j++)
f[i][j]=-INF;
for(ll i=1;i<=n;i++)
f[0][i]=-G[i],head[i]=1;
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&p);
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
scanf("%lld",&r[i][j]);
for(ll i=1;i<=n;i++)
scanf("%lld",&G[i]);
for(ll i=1;i<=m;i++)
for(ll j=1;j<=n;j++)
sum[j][i]=sum[w(j-1)][i-1]+r[w(j-1)][i];
init();
for(ll i=1;i<=m;i++)
{
for(ll st=1;st<=n;st++)
{
while(head[w(st-i+1)]<=tail[w(st-i+1)]&&q[w(st-i+1)][tail[w(st-i+1)]].gs+val(q[w(st-i+1)][tail[w(st-i+1)]].ks,q[w(st-i+1)][tail[w(st-i+1)]].pos,i-q[w(st-i+1)][tail[w(st-i+1)]].pos)<f[i-1][st]+val(st,i-1,1)) tail[w(st-i+1)]--;
q[w(st-i+1)][++tail[w(st-i+1)]]={f[i-1][st],st,i-1};
while(i-q[w(st-i+1)][head[w(st-i+1)]].pos>p) head[w(st-i+1)]++;
}
tzy=-INF;
for(ll j=1;j<=n;j++)
tzy=max(tzy,q[j][head[j]].gs+val(q[j][head[j]].ks,q[j][head[j]].pos,i-q[j][head[j]].pos));
for(ll j=1;j<=n;j++)
f[i][j]=tzy-G[j];
}
for(ll i=1;i<=n;i++)
ans=max(ans,f[m][i]+G[i]);
printf("%lld\n",ans);
return 0;
}