fork(1) download
copy 
  1. #include<fstream>
  2. #include<algorithm>
  3. #include <iostream>
  4. #include<numeric>
  5. #include<utility>
  6. #include<functional>
  7. #include<stdio.h>
  8. #include<assert.h>
  9. #include<memory.h>
  10. #include<bitset>
  11. #include <stack>
  12. #include <queue>
  13. #include <vector>
  14. #include <iterator>
  15. #include <math.h>
  16. #include<cstring>
  17. #include <cmath>
  18. #include <set>
  19. #include <cmath>
  20.  
  21. #define lp(i,n) for(int i=0;i<(int)n;i++)
  22. #define all(v)				((v).begin()), ((v).end())
  23. #define sz(v)				((int)((v).size()))
  24. #define clr(v, d)			memset(v, d, sizeof(v))
  25. #define rep(i, v)		for(int i=0;i<sz(v);++i)
  26. using namespace std;
  27. #define vi vector<int>
  28. #define vd vector<double>
  29. #define fast std::ios_base::sync_with_stdio(false);
  30. #define LL long long
  31.  
  32. int N,M,B,MOD;
  33. int MAXN = 501;
  34. LL memo[501][501];
  35. LL dp[501][501][501];
  36. int arr[501];
  37.  
  38.  
  39.  
  40. int main(){
  41. 	cin >> N >> M >>B >> MOD;
  42. 	for(int i=1;i<=N;i++)cin >> arr[i];
  43. 	clr(memo,-1);
  44. 	clr(dp,0);
  45. 	dp[0][0][0] = 1;
  46.    lp(i,N+1) dp[i][0][0] = 1;
  47.  
  48.  
  49. 	for(int i=1;i<=N;i++){
  50. 		for(int j=1;j<=M;j++){
  51. 			for(int k=0;k<=B;k++){
  52. 				dp[i][j][k] += dp[(i-1)][j][k]%MOD;
  53. 				if(k-arr[i]>=0) dp[(i)][j][k] += (dp[(i)][j-1][k-arr[i]])%MOD;
  54. 			}
  55. 		}
  56. 	}
  57. 	LL sum = 0;
  58. 	lp(i,B+1){
  59. 		sum += (dp[N][M][i]+MOD)%MOD;
  60.  
  61. 	}
  62. 	cout << sum << endl;
  63.  
  64. }
  65.  
  66.  
  67.  
  68.  
  69.  
Runtime error #stdin #stdout 1.07s 987648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/edQhJr
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!