C++14(g++5.4) 解法, 执行用时: 871ms, 内存消耗: 5356K, 提交时间: 2020-04-05 18:16:28

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=455;
int n,m,tot,a[N],b[N],c[N];
bitset<N>pre[M],bk[M];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        if(a[i]!=a[i-1]) b[++tot]=a[i],c[tot]=1;
        else c[tot]++;
    pre[0][0]=bk[tot+1][0]=1;
    for(int i=1;i<=tot;i++)
    {
        pre[i]|=pre[i-1];
        for(int j=1;j<=c[i];j++)
            pre[i]|=pre[i]<<b[i];
    }
    for(int i=tot;i>=1;i--)
    {
        bk[i]|=bk[i+1];
        for(int j=1;j<=c[i];j++)
            bk[i]|=bk[i]<<b[i];
    }
    vector<int>v;
    for(int i=1;i<=tot;i++)
    {
        bool flag=false;
        for(int j=0;j<=m;j++)
            if(pre[i-1][j]&&bk[i+1][m-j])
            {
                flag=true;break;
            }
        if(!flag) v.push_back(b[i]);
    }
    printf("%d\n",v.size());
    for(int x:v) printf("%d ",x);
}

C++ 解法, 执行用时: 255ms, 内存消耗: 2844K, 提交时间: 2021-06-25 17:16:14

#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <bitset>
#include <cstring>
#include <iostream>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ull unsigned long long
int n,m,a[100005],f[100005],len,ans[100005];
bitset<100005>dp[100005];
bool run(int x){
	dp[x][0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]==x)continue;
		dp[x]|=(dp[x]<<a[i]);
		if(dp[x][m])return 0;
	}
	return 1;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],f[a[i]]++;
	for(int i=1;i<=100000;i++)
		if(f[i]&&run(i))ans[++len]=i;
	cout<<len<<endl;
	for(int i=1;i<=len;i++)cout<<ans[i]<<" ";
    return 0;
}