fork download
copy 
  1. /* Sat-Chitta-Ananda */
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define int long long
  6. #define double long double
  7. #define inf (int)1e9
  8. #define f first
  9. #define s second
  10.  
  11. const int MOD = (int)1e9+7;
  12.  
  13. int n, m;
  14. int a[100005];
  15. int dp[100002][101];
  16.  
  17. int memo(int index, int prev)
  18. {
  19. 	if(index == n) return 1;
  20. 	if(a[index] && index && abs(prev - a[index]) > 1) return 0;
  21. 	if(dp[index][prev] != -1) return dp[index][prev];
  22.  
  23. 	int ans = 0;
  24. 	if(a[index] == 0) {
  25. 		int start, end;
  26. 		if(prev == 0) start = 1, end = m;
  27. 		else start = max(prev-1, 1LL), end = min(m, prev+1);
  28.  
  29. 		for(int i = start ; i <= end ; ++i) {
  30. 			ans = (ans + memo(index+1, i) % MOD) % MOD;
  31. 		}
  32. 	}
  33. 	else ans = (ans + memo(index+1, a[index]) % MOD) % MOD;
  34. 	return dp[index][prev] = ans % MOD;
  35. }
  36.  
  37. int32_t main()
  38. {
  39. 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  40.  
  41. 	cin >> n >> m;
  42. 	for(int i = 0 ; i < n ; ++i) cin >> a[i];
  43.  
  44. 	memset(dp, -1, sizeof dp);
  45. 	cout << memo(0, 0) % MOD << '\n';
  46.  
  47. 	return 0;
  48. }
Success #stdin #stdout 0.04s 82680KB
comments (?)
stdin
copy 
10 3
3 0 0 3 0 0 0 0 2 0
stdout
copy 
348
https://ideone.com/ATMahc
language:
C++14 (gcc 8.3)
created:
3 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!