#include <stdio.h>
#define N 2001
#define inf 10000000
#define max(a,b) ((a)>(b)?(a):(b))
int f[N][N],q[N],id[N];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int t,n,maxp,w,ap,bp,as,bs;
scanf("%d",&t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(t--) {
scanf("%d%d%d",&n,&maxp,&w);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0;i<n;++i) {
scanf("%d%d%d%d",&ap,&bp,&as,&bs);
for(int j=0;j<=maxp;++j)f[i][j]=-inf;
if(i<=w)for(int j=0;j<=as;++j)f[i][j]=-ap*j;
if(i>0)for(int j=0;j<=maxp;++j)f[i][j]=max(f[i][j],f[i-1][j]);
if (i==0||i<=w) continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int j=0,l=0,r=-1;j<=maxp;++j) {
int tmp=f[i-w-1][j]+j*ap;
while(l<=r&&q[r]<tmp)--r;
q[++r]=tmp,id[r]=j;
while(l<=r&&id[l]+as<j)++l;
f[i][j]=max(f[i][j],q[l]-j*ap);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int j=maxp,l=0,r=-1;j>=0;--j) {
int tmp=f[i-w-1][j]+j*bp;
while(l<=r&&q[r]<tmp)--r;
q[++r]=tmp,id[r]=j;
while(l<=r&&id[l]-bs>j)++l;
f[i][j]=max(f[i][j],q[l]-j*bp);
}
}
int ans=0;
for(int i=0;i<=maxp;++i)ans=max(ans,f[n-1][i]);
printf("%d\n",ans);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|