记得开O2!!!
记得开O2!!!
记得开O2!!!
我们可以发现这是一个裸的01背包,不过w的值十分大,导致O(nw)T掉
那么我们要考虑性质$w=a*2^b,a\leq10,b\leq30$
那么可以发现如果w过于庞大的话那么久浪费了那么全为零的部分
然后我们可以将w分为两个部分,一个大于等于$2^{15}$,一个小于$2^{15}$
那么我们可以把大于的右移15位,然后就可以分成两个部分dp然后合并即可
#include<bits/stdc++.h>
#pragma GCC optimize("2")
#pragma GCC optimize("3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define Up(i,x,y) for(int i(x);i<=y;++i)
#define Dw(i,y,x) for(int i(y);i>=x;--i)
#define N 111
#define M 3010001
using namespace std;
struct BB{
int n,sum;
int w[N],v[N];
int f[M];
inline void clear(){n=0;memset(f,0,sizeof(f));sum=0;}
inline void insert(int W,int V){w[++n]=W,v[n]=V;sum+=W;}
inline void dp( ){
Up(i,1,n)
Dw(j,sum,w[i])
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
inline void out( ){
Up(i,1,n)
printf("%d %d\n",w[i],v[i]);
}
}f1,f2;
int n,m;
const int P(1<<12);
inline void work( ){
f1.clear( ),f2.clear( );
scanf("%d%d",&n,&m);
if(n==m&&n==-1)exit(0);
int w,v;
Up(i,1,n){
scanf("%d%d",&w,&v);
if((w&(-w))<=P){
f1.insert(w,v);
// printf("f1:%d %d\n",w,v);
}else{
f2.insert(w>>12,v);
// printf("f2:%d %d\n",w,v);
}
}
// puts("f1:");
// f1.out( );
// puts("f2:");
// f2.out( );
// puts("ans:");
f2.sum=min(f2.sum,262144);
f1.dp( );f2.dp( );
int ans(0),fuck;
Up(i,0,f2.sum){
if(m<(i<<12))break;
if(ans<f1.f[min(m-(i<<12),f1.sum)]+f2.f[i]){
ans=f1.f[min(m-(i<<12),f1.sum)]+f2.f[i];
fuck=i;
}
}
printf("%d\n",ans);
}
int main( ){
// freopen("r.in","r",stdin);
// freopen("r.out","w",stdout);
while(1)work( );
}