1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 
 6 #define Infp 0x7fffffff
 7 #define Infn 0x80000000
 8 #define DisCon 1000000000
 9 #define MAX  999999999
10 #define MIN -999999999
11 
12 #define Zero(a) memset(a, 0, sizeof(a))
13 #define Copy(a, b) memcpy(a, b, sizeof(b))
14 #define Pi acos(-1)
15 #define FMAX (1E300)
16 #define FMIN (-1E300)
17 #define feq(a, b) (fabs((a)-(b))<1E-6)
18 #define flq(a, b) ((a)<(b)||feq(a, b))
19 #define RG 1005
20 
21 /**
22 var
23    a,b,f:array[0..100000] of longint;
24    m,s,c,n,t,i,j,l,r,d:longint;
25 /**/
26 
27 __int64 a[100005], b[100005], f[100005];
28 __int64 m, s, c, n, t, l, r;
29 
30 /**
31 procedure insert(x,y:longint);
32 begin
33    while (l<=r)and(b[r]<=y) do dec(r);
34    inc(r);a[r]:=x;b[r]:=y;
35 end;
36 /**/
37 
38 void insert(__int64 x, __int64 y)
39 {
40     while(l<=r&&b[r]<=y)
41         r--;
42     r++;
43     a[r]=x;
44     b[r]=y;
45 }
46 /**
47 begin
48    readln(n,t);              //读入数据 n为物品个数 t为背包容量
49    for i:=1 to n do
50    begin
51       read(m,s,c);         //读入当前物品 m为物品体积、s为物品价值、c为物品可用次数（0表示无限制）
52       if (c=0)or(t div m<c) then c:=t div m;
53       for d:=0 to m-1 do
54       begin
55          l:=1;r:=0;     //清空队列
56          for j:=0 to (t-d) div m do
57          begin
58             insert(j,f[j*m+d]-j*s);   //将新的点插入队列
59             if a[l]<j-c then inc(l);   //删除失效点
60             f[j*m+d]:=b[l]+j*s;        //用队列头的值更新f[j*m+d]
61          end;
62       end;
63    end;
64    writeln(f[t]);
65 end.
66 /**/
67 int main()
68 {
69     scanf("%I64d%I64d", &n, &t);
70     Zero(a);
71     Zero(b);
72     Zero(f);
73 
74     for(__int64 i=1; i<=n; i++)
75     {
76         scanf("%I64d%I64d%I64d", &m, &s, &c);
77         if(c==0||t/m<c)c=t/m;
78         for(__int64 d=0; d<=m-1; d++)
79         {
80             l=1;
81             r=0;
82             for(__int64 j=0; j<=(t-d)/m; j++)
83             {
84                 insert(j, f[j*m+d]-j*s);
85                 if(a[l]<j-c)
86                     l++;
87                 f[j*m+d]=b[l]+j*s;
88             }
89         }
90     }
91     printf("%I64d\n", f[t]);
92 
93     return 0;
94 }

 1     for(__int64 i=1; i<=n; i++)
 2     {
 3         scanf("%I64d%I64d%I64d", &m, &s, &c);
 4         if(c==0||t/m<c)c=t/m;
 5         for(__int64 d=0; d<=m-1; d++)
 6         {
 7             l=1;
 8             r=0;
 9             for(__int64 j=0; j<=(t-d)/m; j++)
10             {
11                 insert(j, f[j*m+d]-j*s);
12                 if(a[l]<j-c)
13                     l++;
14                 f[j*m+d]=b[l]+j*s;
15             }
16         }
17     }
18     printf("%I64d\n", f[t]);