f[i][j] = max(f[i-1][j-w*k]+v*k)
令j = d + k' * w
f[i][d + k' * w] = max(f[i - 1][d - (k - k') * w] + v * (k - k')) + v * k'
(k - k’) 最多在min(m, W / w) 范围内
单调队列维护

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxw = 4e4 + 10, inf = 0x3f3f3f3f;
int n, W, ret, ans, f[maxw], q[maxw], id[maxw];
void init(){
    memset(f, 0, sizeof(f));
    scanf("%d%d", &n, &W);
    for(int i = 1, v, w, m; i <= n; i++){
        scanf("%d%d%d", &w, &v, &m);
        if(w == 0){ ans += m * v; continue; }
        m = min(m, W / w);
        for(int d = 0; d < w; d++){
            int maxk = (W - d) / w, h = 1, t = 0;
            for(int k = 0; k <= maxk; k++){
                int pr = f[d + k * w] - k * v;
                while(h <= t && pr >= q[t]) t--;
                q[++t] = pr; id[t] = k;
                while(h <= t && id[h] + m < k) h++;
                f[d + k * w] = max(f[d + k * w], q[h] + k * v);
                ret = max(ret, f[d + k * w]);
            }
        }
    }
    ans += ret;
    printf("%d\n", ans);
    return;
}
void solve(){

}
int main(){
//  freopen("ex.in", "r", stdin);
//  freopen("ex.out", "w", stdout);
    init(); solve();
    return 0;
}