求助,BZOJ AC ,Luogu WA 1

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define Set(a,b) memset(a,b,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(a))
using namespace std;
typedef long long ll;
template <typename T> inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
int n,W;
const int N=102;
const int MAXN=1501;
struct Item{
	int val,a,b;
	void divide(){b=0;while(!(a&1)) a>>=1,++b;}
	Item(){}
	Item(int _val,int _a,int _b){val=_val,a=_a,b=_b;}
	inline bool operator <(Item B)const{return b<B.b;}
}A[N];
ll dp[MAXN],f[2][MAXN];
ll bac[31][MAXN];
ll Ma[31],bin[31];
int main()
{
	bin[0]=1;
	for(int i=1;i<=30;++i) bin[i]=bin[i-1]<<1;
	while(scanf("%d %d",&n,&W)) {
		if(n==-1&&W==-1) break;
		Set(dp,0);Set(bac,0);Set(Ma,0);int val,a,b;
		for(int i=1;i<=n;++i) {init(a);init(val);A[i]=Item(val,a,0);A[i].divide();}
		sort(A+1,A+1+n);
		for(int H=1,P=1;H<=n;++H,P=H) {
			while(A[H].b==A[H+1].b&&H<n) ++H;
			ll sum=0;Set(dp,0);
			for(int i=P;i<=H;++i) {sum+=A[i].a;for(int j=sum;j>=A[i].a;--j) dp[j]=max(dp[j],dp[j-A[i].a]+A[i].val);}
			Ma[A[H].b]=sum;Copy(bac[A[H].b],dp);
		}
		int i=0;Set(f,0);int cnt=0;Copy(f[cnt],bac[0]);
		f[cnt][Ma[0]+1]=f[cnt][Ma[0]];
		for(i=1;i<=30;++i) {
			if(bin[i]>W) break;
			cnt^=1;ll retu=W%bin[i],retv=W%bin[i-1];
			ll Up=Ma[i]+(Ma[i-1]>>1)+1;
			for(ll j=0;j<=Up;++j) {//上界会有问题?
				f[cnt][j]=0;register ll NOWMAX=(j<<i)+retu-retv;
				register ll res,ret;ret=NOWMAX;ret>>=i-1;
				f[cnt][j]=f[cnt^1][min(Ma[i-1],ret)];
				for(ll k=0;k<=Ma[i];++k) {
					res=k<<i;ret=NOWMAX-res;if(ret<0) break;else ret>>=i-1;
					f[cnt][j]=max(f[cnt][j],f[cnt^1][min(Ma[i-1],ret)]+bac[i][k]);
				}
			}
			Ma[i]=Up;
		}
		ll ans=0;ans=f[cnt][1];
		printf("%lld\n",ans);
	}
}