1. #include <iostream>
    2. using namespace std;
    4. class PackSolver {
    5.     static const int MAXN = 1000 + 5;
    6.     struct Node {
    7.         int pos, val;
    8.     } q[MAXN];
    9.     int dp[MAXN] = {};
    10.     int N, V;
    12.     void zeroOnePack(int v, int w) {
    13.         for (int i = V; i >= v; i--)
    14.             dp[i] = max(dp[i], dp[i - v] + w);
    15.     }
    17.     void completePack(int v, int w) {
    18.         for (int i = v; i <= V; i++)
    19.             dp[i] = max(dp[i], dp[i - v] + w);
    20.     }
    22.     // 多重背包 N*V
    23.     void multiPack(int v, int w, int s) {
    24.         for (int i = 0; i < v; i++) {
    25.             int hh = 0, tt = 0, stop = (V-i)/v;
    26.             for (int k = 0; k <= stop; k++) {
    27.                 int val = dp[k*v+i] - k * w;
    28.                 while (hh < tt && q[tt - 1].val <= val) tt--;
    29.                 if (hh < tt && k - q[hh].pos > s) hh++;
    30.                 q[tt].val = val, q[tt++].pos = k;
    31.                 dp[k*v+i] = q[hh].val + k*w;
    32.             }
    33.         }
    34.     }
    36.     // 多重背包 N*V*LogS
    37.     void multiPack(int v, int w, int s, bool) {
    38.         for (int i = 1; i <= s; s -= i, i *= 2) zeroOnePack(v * i, w * i);
    39.         if (s) zeroOnePack(v * s, w * s);
    40.     }
    42. public:
    43.     void f() {
    44.         cin >> N >> V;
    45.         int v, w, s;
    46.         while (N--) {
    47.             cin >> v >> w >> s;
    48.             if (s == -1) zeroOnePack(v, w);
    49.             else if (s == 0) completePack(v, w);
    50.             else multiPack(v, w, s);
    51.         }
    52.         cout << dp[V] << endl;
    53.     }
    54. };
    56. int main() {
    57.     PackSolver s;
    58.     s.f();
    59. }