Description
有n个物品，m块钱，给定每个物品的价格，求买物品的方案数。
Input
第一行两个数n，m代表物品数量及钱数
第二行n个数，代表每个物品的价格
n<=40，m<=10^18
Output
一行一个数表示购买的方案数
（想怎么买就怎么买，当然不买也算一种）
Sample Input
5 1000
100 1500 500 500 1000
100 1500 500 500 1000
Sample Output
8
正解：$meet \ in \ the \ middle$。
比较裸的$meet \ in \ the \ middle$，搜索完以后直接把两个栈按照价值排序，用单调指针扫一扫就行了。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define il inline
#define RG register
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; ll st1[],st2[],a[],n,m,ans,top1,top2; il ll gi(){
RG ll x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} il void dfs1(RG ll x,RG ll cost){
if (x>n/){ st1[++top1]=cost; return; }
dfs1(x+,cost),dfs1(x+,cost+a[x]); return;
} il void dfs2(RG ll x,RG ll cost){
if (x>n){ st2[++top2]=cost; return; }
dfs2(x+,cost),dfs2(x+,cost+a[x]); return;
} il void work(){
n=gi(),m=gi(); for (RG ll i=;i<=n;++i) a[i]=gi();
dfs1(,),dfs2(n/+,);
sort(st1+,st1+top1+),sort(st2+,st2+top2+);
for (RG ll i=,j=top2;i<=top1;++i){
while (j && st1[i]+st2[j]>m) j--; ans+=j;
}
printf("%lld\n",ans); return;
} int main(){
File("championship");
work();
return ;
}