fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. #include<utility>
  5. #include<algorithm>
  6. #include<map>
  7. #include<queue>
  8. #include<stack>
  9. #include<vector>
  10. #include<string>
  11. #include<cmath>
  12.  
  13. #define gi(x) scanf("%d",&x)
  14. #define pi(x) printf("%d ",x)
  15. #define pin(x) printf("%d\n",x);
  16. #define mp make_pair
  17. #define fi first
  18. #define se second
  19.  
  20. using namespace std;
  21.  
  22. const int lim = 2005;
  23. typedef long long LL;
  24. typedef pair<int,int> pii;
  25. int n,h;
  26. int a[lim];
  27. LL dp[lim][lim];
  28.  
  29. void fill_dp()
  30. {
  31. 	for(int i=0;i<lim;i++)
  32. 		for(int j=00;j<lim;j++)
  33. 			dp[i][j]=(LL)0;
  34. 	if(a[0] == h-1 || a[0] == h)
  35. 		dp[0][0] = (LL)1;
  36. 	if(a[0] == h-1)
  37. 		dp[0][1] = (LL)1;
  38. 	for(int i=1;i<n;i++)
  39. 	{
  40. 		for(int j=0;j<=i+1;j++)
  41. 		{
  42. 			if(a[i] + j == h)
  43. 			{
  44. 				dp[i][j] += dp[i-1][j-1];
  45. 				dp[i][j] += dp[i-1][j];
  46. 			}
  47. 			if(a[i] + j == h-1)
  48. 			{
  49. 				dp[i][j] += (LL)dp[i-1][j+1]*(j+1);
  50. 				dp[i][j] += dp[i-1][j];
  51. 				dp[i][j] += (LL)dp[i-1][j]*j;
  52. 			}
  53. 		}
  54. 	}
  55. }
  56.  
  57.  
  58. int main()
  59. {
  60.     cin >> n;
  61. 	cin >> h;
  62. 	for(int i=0;i<n;i++)
  63. 	{
  64. 		cin >> a[i];
  65. 	}
  66. 	fill_dp();
  67. 	cout << dp[n-1][0] << "\n";
  68.     return 0;    
  69. }
  70.  
Success #stdin #stdout 0.02s 34152KB
comments (?)
stdin
copy 
5 1
1 1 1 1 1
stdout
copy 
1
https://ideone.com/IT1zYn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!