cdq+多重背包单调队列优化
那个前缀后缀合并的是真的不靠谱(这明显T的啊)
#include<cstdio>
#include<algorithm>
#include<vector>
#define pr pair<int,int>
#define mp make_pair
#define fr first
#define sc second
using namespace std;
int n,qe,m=1000,ans[300005],F[4005][1005],w[1005],v[1005],c[1005];
vector<pr> vec[1005];
struct node{
int fr,sc;
}q[1005];
void update(int t,int i){
for (int d=0; d<v[i]; d++){
int head=1,tail=0;
for (int j=0; v[i]*j+d<=m; j++){
int now=v[i]*j+d;
while (head<=tail && q[tail].sc<=F[t][now]-j*w[i]) tail--;
q[++tail]=(node){j,F[t][now]-j*w[i]};
while (head<=tail && q[head].fr<j-c[i]) head++;
F[t][now]=0;
if (head<=tail) F[t][now]=q[head].sc+j*w[i];
}
}
}
void solve(int t,int l,int r){
if (l==r){
for (int i=1; i<=m; i++) F[t][i]=max(F[t][i],F[t][i-1]);
for (int i=0; i<(int)vec[l].size(); i++) ans[vec[l][i].fr]=F[t][vec[l][i].sc];
return;
}
int mid=(l+r)>>1;
for (int i=0; i<=m; i++) F[t<<1][i]=F[t<<1|1][i]=F[t][i];
for (int i=mid+1; i<=r; i++) update(t<<1,i);
solve(t<<1,l,mid);
for (int i=l; i<=mid; i++) update(t<<1|1,i);
solve(t<<1|1,mid+1,r);
}
int main(){
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);
scanf("%d",&qe);
for (int i=1; i<=qe; i++){
int x,y;
scanf("%d%d",&x,&y);
x++;
vec[x].push_back(mp(i,y));
}
solve(1,1,n);
for (int i=1; i<=qe; i++) printf("%d
",ans[i]);
return 0;
}