hdu 3401

 1 //#include<bits/stdc++.h>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<queue>
 7 #define inc(i,l,r) for(int i=l;i<=r;i++)
 8 #define dec(i,l,r) for(int i=l;i>=r;i--)
 9 #define link(x) for(edge *j=h[x];j;j=j->next)
10 #define mem(a) memset(a,0,sizeof(a))
11 #define inf 1e9
12 #define ll long long
13 #define succ(x) (1<<x)
14 #define NM 2000+5
15 using namespace std;
16 int read(){
17     int x=0,f=1;char ch=getchar();
18     while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
19     while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
20     return x*f;
21 }
22 int T,n,m,w,ans,f[NM][NM],q[NM],qh,qt,_x,_y,x,y;
23 int main(){
24 //    freopen("data.in","r",stdin);
25     T=read();
26     while(T--){
27         n=read();m=read();w=read();ans=0;mem(f);mem(q);
28         inc(i,1,m)f[0][i]=-inf;
29         inc(i,1,w){
30             x=read();y=read();_x=read();_y=read();
31             inc(j,0,m)f[i][j]=f[i-1][j];
32             inc(j,0,min(_x,m))
33             f[i][j]=max(f[i][j],-j*x);
34 //            inc(j,1,m)printf("%d ",f[i][j]);printf("\n");
35         }
36         inc(i,w+1,n){
37             y=read();x=read();_y=read();_x=read();
38             qh=1;qt=0;mem(q);
39             inc(j,0,m)f[i][j]=f[i-1][j];
40             dec(j,m,1){
41                 while(qh<=qt&&f[i-w-1][q[qt]]+x*q[qt]<=f[i-w-1][j]+x*j)qt--;
42                 while(qh<=qt&&q[qh]>j+_x-1)qh++;
43                 q[++qt]=j;int t=q[qh];
44                 f[i][j-1]=max(f[i][j-1],f[i-w-1][t]+x*t-(j-1)*x);
45             }//sell
46             qh=1;qt==0;mem(q);
47             inc(j,0,m-1){
48                 while(qh<=qt&&f[i-w-1][q[qt]]+y*q[qt]<=f[i-w-1][j]+y*j)qt--;
49                 while(qh<=qt&&q[qh]<j-_y+1)qh++;
50                 q[++qt]=j;int t=q[qh];
51                 f[i][j+1]=max(f[i][j+1],f[i-w-1][t]+y*t-(j+1)*y);
52             }//buy
53 //            inc(j,0,m)printf("%d ",f[i][j]);printf("\n");
54         }
55         inc(i,0,m)ans=max(ans,f[n][i]);
56         printf("%d\n",ans);
57     }
58     return 0;
59 }