【BZOJ4800】[Ceoi2015]Ice Hockey World Championship （meet in the middle)
题面
题解
裸题吧，顺手写一下。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
inline ll read()
{
ll x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,K;
ll ans,m,a[50],s1[1050000],s2[1050000];
int t1,t2;
void dfs1(int x,ll s)
{
if(s>m)return;
if(x==K+1){s1[++t1]=s;return;}
dfs1(x+1,s);dfs1(x+1,s+a[x]);
}
void dfs2(int x,ll s)
{
if(s>m)return;
if(x==n+1){s2[++t2]=s;return;}
dfs2(x+1,s);dfs2(x+1,s+a[x]);
}
int main()
{
n=read();m=read();K=n/2;
for(int i=1;i<=n;++i)a[i]=read();
dfs1(1,0);dfs2(K+1,0);
sort(&s1[1],&s1[t1+1]);sort(&s2[1],&s2[t2+1]);
for(int i=1,j=t2;i<=t1;++i)
{
while(j&&s1[i]+s2[j]>m)--j;
ans+=j;
}
cout<<ans<<endl;
return 0;
}