C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 380K, 提交时间: 2020-09-05 15:30:01

#include<bits/stdc++.h>
using namespace std;
long long a[3005],s[3005],dp[3005];
long long ans=0;
int main()
{
    long long n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",a+i);
    sort(a+1,a+n+1);
    s[1]=a[1];
    for(int i=2;i<=n;i++)s[i]=s[i-1]+a[i];
    dp[0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=max(m-a[i]+1,s[i-1]);j<=m;j++)ans+=dp[j-s[i-1]];
        for(int j=m;j>=a[i];j--)dp[j]+=dp[j-a[i]];
    }
    cout<<ans<<endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 456K, 提交时间: 2022-10-02 14:50:13

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,a[3005],sum[3005];
long long ans,dp[3005];
bool cmp(int x,int y){
	return x>y;
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+1+n,cmp);
	for(i=n;i>0;--i) sum[i]=sum[i+1]+a[i];
	dp[0]=1;
	for(i=1;i<=n;++i){
		for(j=m;j>-1;--j){
			if(m<a[i]) break;
			if(j+sum[i+1]>m-a[i]&&j+sum[i+1]<=m) ans+=dp[j];
	    }
		for(j=m;j>=a[i];--j) dp[j]+=dp[j-a[i]];
	}
	printf("%lld",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-09-06 12:20:01

#include <bits/stdc++.h>
using namespace std;
int n,m;long long f[3010],a[3010],ans,s[3010];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+a[i];
	f[0]=1;
	for(int i=n;i>=1;i--)
	{
		for(int j=max(m-s[i]+1,(long long )0);j<=m-s[i-1];j++)
			ans+=f[j];
		for(int j=m;j>=a[i];j--)
			f[j]+=f[j-a[i]];
	}
	printf("%lld",ans);
}