卡常卡吐了

记录

代码附上了，搜索题，加了inline和register之后是负优化

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 50;
map <LL,int> mp;
LL m,n,a[N],sum;
int minn = 105;
LL f(LL x){
	LL res = 0;
	for(int i=x;i<=n;i++) res += a[i];
	return res;
}
void dfs1(LL pos,LL val,int num){
	if(pos == n / 2 + 1){
		if(!mp[val]){
			if(num == 0) mp[val] = -1;
			else mp[val] = num;
		}
		else mp[val] = min(mp[val],num);
		return;
	}
	if(val > m) return;
	if(val  + f(pos) < m) return; 
	dfs1(pos+1,val,num);
	dfs1(pos+1,val+a[pos],num);
	dfs1(pos+1,val+a[pos]/2,num+1);
}
void dfs2(LL pos,LL val,int num){
	if(pos == n + 1){
		if(mp[m - val] && mp[m - val] != -1)
			minn = min(mp[m - val] + num,minn);
		else if(mp[m - val] == -1)
		    minn = min(num,minn);
		return;
	}
	if(val > m) return;
	if(val + f(pos) + sum < m) return;
	dfs2(pos+1,val,num);
	dfs2(pos+1,val+a[pos],num);
	dfs2(pos+1,val+a[pos]/2,num+1);
}
bool cmp(LL x,LL y){
	return x > y;
}
int main(){
	scanf("%lld%lld",&n,&m);
	m *= 2;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i] *= 2;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n/2;i++) sum += a[i];
	//for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	//cout<<endl; 
	dfs1(1,0,0);
	dfs2(n/2 + 1,0,0);
	if(minn != 105) printf("%d\n",minn);
	else puts("-1");
	return 0;
}