提交记录

// Problem: P9234 [蓝桥杯 2023 省 A] 买瓜
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9234
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date: 2024/08/13 10:59:29
// Author: Li_Feiy
#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)a[i]=read()*2
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
CI N=2e5+5;
int n,m,ans=LLONG_MAX,a[N];
std::unordered_map<int,int> mp;
void dfs1(int step,int sum,int cnt) {
	if(sum>m||cnt>ans) return ;
	if(sum==m) {ans=std::min(ans,cnt);return ;}
	if(step>(n>>1)) {
		if(sum<m) mp[sum]=(!mp[sum]?cnt:std::min(mp[sum],cnt));
		return ;
	}
	dfs1(step+1,sum,cnt);
	dfs1(step+1,sum+a[step],cnt);
	dfs1(step+1,sum+(a[step]>>1),cnt+1);
}
void dfs2(int step,int sum,int cnt) {
	if(sum>m||cnt>ans) return ;
	if(sum==m) {ans=std::min(ans,cnt);return ;}
	if(step>n) {
		if(mp[m-sum]&&m-sum>=0) ans=std::min(ans,mp[m-sum]+cnt);
		return ;
	}
	dfs2(step+1,sum,cnt);
	dfs2(step+1,sum+a[step],cnt);
	dfs2(step+1,sum+(a[step]>>1),cnt+1);
}
signed main() {
	n=read(),m=read()*2;
	arrin(a,n);
	std::sort(arrall(a,n),std::greater<int>());
	dfs1(1,0,0);
	dfs2((n>>1)+1,0,0);
	if(ans==LLONG_MAX) puts("-1");
	else std::cout<<ans;
    return 0;
}