学步园

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define INF 0xfffffff
using namespace std;
struct St
{
    int v,k;
    St(int a=0,int b=0){v=a;k=b;}
}st[2009];
int dp[2009][2009];

int main()
{
    ios::sync_with_stdio(false);
    int t,maxp,w;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d",&t,&maxp,&w);
        int i,j,k;
        int ap,bp,as,bs;
        int pre,nowv,nowk,head,tail;
        for(i=0;i<=t;i++) for(j=0;j<=maxp;j++) dp[i][j]=-INF;
        dp[0][0]=0;
        for(i=1;i<=t;i++)
        {
            scanf("%d %d %d %d",&ap,&bp,&as,&bs);
            if(i<=w+1)
            {
                for(j=0;j<=min(as,maxp);j++) dp[i][j]=max(dp[i-1][0]-j*ap,dp[i-1][j]);
                for(;j<=maxp;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
                continue;
            }
            for(j=0;j<=maxp;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
            pre=i-w-1;
            head=1;tail=0;
            for(j=0;j<=maxp;j++)
            {
                nowv=dp[pre][j]+j*ap;
                nowk=j;
                while(head<=tail && st[tail].v<nowv) tail--;
                tail++;st[tail]=St(nowv,nowk);
                while(head<=tail && st[head].k<j-as) head++;
                dp[i][j]=max(dp[i][j],st[head].v-j*ap);
            }
            head=1;tail=0;
            for(j=maxp;j>=0;j--)
            {
                nowv=dp[pre][j]+j*bp;
                nowk=j;
                while(head<=tail && st[tail].v<nowv) tail--;
                tail++;st[tail]=St(nowv,nowk);
                while(head<=tail && st[head].k>bs+j) head++;
                dp[i][j]=max(dp[i][j],st[head].v-j*bp);
            }
        }
/*
        for(i=1;i<=t;i++)
        {
            for(j=0;j<=maxp;j++) printf("%d ",dp[i][j]);
            printf("\n");
        }
*/
        int ans=-INF;
        for(i=0;i<=maxp;i++) ans=max(ans,dp[t][i]);
        printf("%d\n",ans);
    }
    return 0;
}