在第三个捆绑测试 WA 了一个点,对应代码里的 Sub1,请问有 dalao 帮一下萌新吗 qwq
#include<bits/stdc++.h>
using namespace std;
int a[20];
int b[1000100],s[1000100];
int f[1<<18];
int ans;
int n,v,x;
namespace Sub1 {
int t[1<<18];
set<int> st;
void add(int cur)
{
for(int i=0; i<x; i++)
if(!((cur>>i)&1))
{
int sta=cur|1<<i;
++t[sta];
if(t[sta]==__builtin_popcount(sta))
st.insert(sta);
}
}
void work()
{
f[0]=1; add(0); st.insert(-1);
for(int i=1; i<=n; i++)
for(auto p=st.begin(); p!=st.end(); ++p)
{
int cur=*p;
if(__builtin_popcount(cur^(cur&b[i]))+s[i]<=v)
{
f[cur]=1;
add(cur); --p;
st.erase(cur);
}
}
}
}
namespace Sub2 {
vector<int> t[19][1<<18]; // 桶
void work()
{
f[0]=1;
for(int i=0; i<1<<x; i++) t[0][i].push_back(0);
for(int i=1; i<=n; i++)
for(int j=0; j<=min(v-s[i], x); j++)
{
for(int cur : t[j][b[i]])
if(!f[cur|b[i]])
for(int k=cur|b[i]; k; k=(cur|b[i])&(k-1))
if(!f[k])
{
f[k]=1;
int ccur=((1<<x)-1)^k,num=__builtin_popcount(k);
for(int sta=ccur; sta; sta=ccur&(sta-1))
t[num][sta].push_back(k);
}
t[j][b[i]].clear();
}
}
}
int main()
{
cin>>n>>v>>x;
for(int i=0; i<x; i++)
scanf("%d", &a[i]);
for(int i=1; i<=n; i++)
for(int j=0; j<x; j++)
{
int c;
scanf("%d", &c);
if(c) b[i]|=1<<j;
s[i]+=c;
}
if(n<=2e3)
Sub1::work();
else
Sub2::work();
for(int i=0; i<1<<x; i++)
if(f[i])
{
int sum=0;
for(int j=0; j<x; j++)
if((i>>j)&1)
sum+=a[j];
ans=max(ans, sum);
}
cout<<ans;
return 0;
}