fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int dp[505][505][505];
  5.  
  6. int main(){
  7.  
  8. 	int n,m,b;
  9. 	long int mod;
  10. 	cin>>n>>m>>b>>mod;
  11.  
  12. 	int bug[n+1],i,j,k;
  13.  
  14. 	for(i=0;i<n;i++)
  15. 		cin>>bug[i];
  16.  
  17. 	int cnt=0;
  18.  
  19. 	dp[0][0][0]=1;
  20.  
  21. 	for(i=1;i<=n;i++)
  22. 		dp[i][0][0]=1;
  23.  
  24. 	for(i=1;i<=n;i++){
  25. 		for(j=1;j<=m;j++){
  26. 			for(k=0;k<=b;k++){
  27. 				// either this ith programmer writes this line or doesnot
  28. 				dp[i][j][k]= dp[i-1][j][k]; // programmer doesnot write
  29.  
  30. 				if((k>=bug[i-1]))
  31. 				dp[i][j][k]+= dp[i][j-1][k-bug[i-1]];  // programmer writes
  32.  
  33. 				dp[i][j][k]%=mod;
  34. 			}
  35. 		}
  36. 	}
  37.  
  38. //	for(i=1;i<=n;i++){
  39. 		for(j=0;j<=b;j++){
  40. 			cnt+= dp[n][m][j];
  41. 			cnt%=mod;
  42. //	}
  43. 	}
  44.  
  45. 	cout<<cnt<<endl;
  46.  
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 506240KB
comments (?)
stdin
copy 
3 5 6 11
1 2 1
stdout
copy 
0
https://ideone.com/PpcGob
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!