fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e2 + 5; 
  12. const int K = 1e5 + 5; 
  13. const int MOD = 1e9 + 7;  
  14.  
  15. void add(int& a, int b) {
  16. 	a += b; 
  17. 	if (a >= MOD) a -= MOD; 
  18. 	if (a < 0) a += MOD; 
  19. }
  20.  
  21. int n, k;  
  22. int a[N]; 
  23. int dp[N][K];  // dp[i][j] = Số cách chia j cây kẹo cho i đứa trẻ đầu tiên 
  24. int sum[N][K]; // sum[i][j] = Tổng các dp[i][1] + dp[i][2] + ... + dp[i][j]
  25.  
  26. int getSum(int i, int lj, int rj) {
  27. 	int ans = sum[i][rj]; 
  28. 	if (lj - 1 >= 0) add(ans, -sum[i][lj - 1]);  
  29. 	return ans;  
  30. }
  31.  
  32. int main() {
  33. 	ios::sync_with_stdio(false); 
  34. 	cin.tie(nullptr);  	
  35. 	cin >> n >> k; 
  36. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  37.  
  38. 	dp[0][0] = 1;   
  39. 	for (int j = 0; j <= k; j++) sum[0][j] = 1; 
  40.  
  41. 	for (int i = 1; i <= n; i++) {
  42. 		for (int j = 0; j <= k; j++) {
  43. 			// for (int x = 0; x <= a[i]; x++) {
  44. 			// 	if (j - x >= 0) add(dp[i][j], dp[i - 1][j - x]); 
  45. 			// }
  46. 			dp[i][j] = getSum(i - 1, j - a[i], j); 
  47. 			sum[i][j] = dp[i][j]; 
  48. 		}
  49.  
  50.  		for (int j = 1; j <= k; j++) add(sum[i][j], sum[i][j - 1]); 
  51. 	}
  52.  
  53. 	cout << dp[n][k] << '\n'; 
  54. }
Success #stdin #stdout 0.01s 5564KB
comments (?)
stdin 
3 4
1 2 3
stdout 
5
https://ideone.com/iB2LO3
language:
C++14 (gcc 8.3)
created:
39 days 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!