1 solutions

  • 0
    @ 2022-12-31 16:05:48

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    
    #define LL long long
    
    const LL N=51,M=2501;
    
    LL n,k,a[N],f[N][M][N];
    
    int main(){
    	scanf("%lld%lld",&n,&k);
    	for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);
    	for(LL i=0;i<N;i++) f[i][0][0]=1;
    	for(LL i=1;i<=n;i++){
    		for(LL j=0;j<M;j++){
    			for(LL k=0;k<=i;k++){
    				f[i][j][k]=f[i-1][j][k];
    				if(j>=a[i]&&k>=1) f[i][j][k]+=f[i-1][j-a[i]][k-1];
    			}
    		}
    	}
    	LL ans=0;
    	for(LL i=1;i<=n;i++){
    		for(LL j=0;j<i;j++){
    			LL sum=(j+1)*k-a[i];
    			if(sum>=0) ans+=f[i-1][sum][j];
    		}
    	}
    	printf("%lld\n",ans);
    }
    

    Python :

    # coding=utf-8
    N, A = map(int, input().split())
    Xs = list(map(int, input().split()))
    
    Ys = [X-A for X in Xs]
    sumPos = sumNeg = 0
    for Y in Ys:
        if Y >= 0:
            sumPos += Y
        else:
            sumNeg += Y
    #print('# sumPos:', sumPos, '/ sumNeg:', sumNeg)
    
    LLL = sumPos - sumNeg + 1
    
    dp = [0] * (LLL+1)
    dp[0] = 1
    for Y in Ys:
        dp2 = dp[:]
        for s in range(sumNeg, sumPos+1):
            dpNow = dp[s]
            if dpNow == 0:
                continue
            s2 = s+Y
            dp2[s2] += dpNow
        dp = dp2
    #    print('# Y:', Y, '/ dp:', dp)
    
    ans = dp[0] - 1
    print(ans)
    
    • 1

    Information

    ID
    20988
    Time
    2000ms
    Memory
    128MiB
    Difficulty
    8
    Tags
    (None)
    # Submissions
    95
    Accepted
    15
    Uploaded By