前面有大佬说是dp数组赋值的问题,但是改成了-1e18还是错的TAT
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4010;
int T,maxP,W;
int ap[N],bp[N],as[N],bs[N];
int dp[N][N];
signed main(){
scanf("%lld%lld%lld",&T,&maxP,&W);
for(int i=1;i<=T;i++){
scanf("%lld%lld%lld%lld",&ap[i],&bp[i],&as[i],&bs[i]);
}
for(int i=0;i<=T;i++){
for(int j=0;j<=maxP;j++){
dp[i][j]=-1e18;
}
}
dp[0][0]=0;
deque<int> q1;
deque<int> q2;
for(int i=1;i<=T;i++){
for(int j=0;j<=as[i];j++){
dp[i][j]=-j*ap[i];
}
if(i>1){
for(int j=0;j<=maxP;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j]);
}
}
if(i<=W) continue;
while(!q1.empty()) q1.pop_back();
for(int j=0;j<=maxP;j++){
while(!q1.empty()&&q1.front()<j-as[i]) q1.pop_front();
while(!q1.empty()&&dp[i-W-1][q1.back()]+q1.back()*ap[i]<dp[i-W-1][j]+j*ap[j]) q1.pop_back();
q1.push_back(j);
if(!q1.empty()){
dp[i][j]=max(dp[i][j],dp[i-W-1][q1.front()]-ap[i]*(j-q1.front()));
}
}
while(!q2.empty()) q2.pop_back();
for(int j=maxP;j>=0;j--){
while(!q2.empty()&&q2.front()>j+bs[i]) q2.pop_front();
while(!q2.empty()&&dp[i-W-1][q2.back()]+q2.back()*bp[i]<dp[i-W-1][j]+j*bp[i]) q2.pop_back();
q2.push_back(j);
if(!q2.empty()){
dp[i][j]=max(dp[i][j],dp[i-W-1][q2.front()]+bp[i]*(q2.front()-j));
}
}
}
cout<<dp[T][0];
return 0;
}