考虑思考完全背包问题的过程。完全背包其实是一个前缀最值的过程。而完全背包就是滑动窗口问题。可以把余数相同的归为一类，然后就可以直接单调队列了，队长 \(s\)。
#include<cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
const int N=20001;
int n,m,f[N],g[N],q[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i){
int v,w,s;
scanf("%d%d%d",&v,&w,&s);
for(int j=0;j<=m;++j)g[j]=f[j];
for(int j=0;j<v;++j){//注意这个两重循环是 O(m)，因为每个余数都枚举到了，只是整合成一块了。
int hh=0,tt=-1;
for(int k=j;k<=m;k+=v){//单调队列优化
if(hh<=tt&&q[hh]<k-s*v)++hh;
if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w)--tt;
q[++tt]=k;
}
}
}
printf("%d",f[m]);
return 0;
}