一道多重背包模版

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=120005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
} 
bool f[N];int a[7]; 
int main()
{
    while(qr(a[1]),qr(a[2]),qr(a[3]),qr(a[4]),qr(a[5]),qr(a[6]),a[1]+a[2]+a[3]+a[4]+a[5]+a[6])
    {
        int sum=a[1]+a[2]*2+a[3]*3+a[4]*4+a[5]*5+a[6]*6;
        if(sum&1){puts("Can't");continue;}//判断中位数是否可行
        sum>>=1;memset(f,0,sum+1);f[0]=1;
        for(int i=1;i<=6;i++)
        {
            if(!a[i])continue;
            int b=1,p=0;
            for(;b<=a[i];b+=1<<(++p));
            b-=1<<p;p--;int r=a[i]-b;
            for(int t=0;t<=p;t++)
            {
                int w=1<<t;w*=i;
                for(int j=sum;j>=w;j--)
                    f[j]|=f[j-w];
            }
            int w=r*i;
            for(int j=sum;j>=w;j--)f[j]|=f[j-w];
        }
        if(f[sum])puts("Can");
        else puts("Can't");
    }
    return 0;
}