上代码

#include<bits/stdc++.h>
using namespace std;
long long f1[100001][1001],f2[100001][1001],n,m,c,ji;
struct node{
    long long s,id;
}w[300001],v[300001];
inline int read(){
	register int x=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		int cw=read(),cv=read(),c=read(),now=1;
		while(now<=c){
			w[++ji].s=cw*now,v[ji].s=cv*now;
            w[ji].id=i,v[ji].id=i;
			c-=now,now*=2;
		}if(c){
			w[++ji].s=cw*c,v[ji].s=cv*c;
            w[ji].id=i,v[ji].id=i;
		}
	}cin>>m;
	n=ji;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=1000;j++)f1[i][j]=f1[i-1][j];
		for(int j=1000;j>=w[i].s;j--){
			f1[i][j]=max(f1[i][j],f1[i-1][j-w[i].s]+v[i].s);
		}
	}for(int i=n;i>=1;i--){
		for(int j=0;j<=1000;j++)f2[i][j]=f2[i+1][j];
		for(int j=1000;j>=w[i].s;j--){
			f2[i][j]=max(f2[i][j],f2[i+1][j-w[i].s]+v[i].s);
		}
	}for(int k=1;k<=m;k++){
		int cn=read()+1,V=read();
		long long ans=0;
        int l=0,r=0;
        while(w[l+1].id<cn&&l<n)++l;
        r=l;
        while(w[r+1].id<=cn&&r<n)++r;
		for(int j=0;j<=V;j++){
			ans=max(ans,f1[l][j]+f2[r+1][V-j]);
		}cout<<ans<<endl;
	}
}