fork download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int maxN=1e5;
  5. const int maxM=100;
  6. const long mod=1e9+7;
  7. typedef long long int ll;
  8. int N, M;
  9. int arr[maxN+5];
  10. ll dp[maxN+5][maxM+1]; // dp[n][m]= 從左開始，第n個數字為m的方法數
  11. // dp[n][m] = dp[n-1][m-1] + dp[n-1][m] + dp[n-1][m+1]
  12.  
  13. void add(int n,int m){
  14. 	for(int i=-1;i<=1;i++){
  15. 		if( 0< m+i and m+i<=M ){
  16. 			dp[n][m]+=dp[n-1][m+i];
  17. 			dp[n][m]%=mod;
  18. 		}	
  19. 	}
  20. }
  21.  
  22. int main() {
  23. 	cin>>N>>M;
  24. 	for(int i=0;i<N;i++)
  25. 		cin>>arr[i];
  26. 	for(int i=0;i<N;i++){
  27. 		for(int j=0;j<=M;j++)
  28. 			dp[i][j]=0;
  29. 	}	
  30.  
  31. 	// first number
  32. 	if( arr[0]==0 ){
  33. 		for(int j=1;j<=M;j++)
  34. 			dp[0][j]=1;
  35. 	}
  36. 	else{
  37. 		dp[0][ arr[0] ]=1;
  38. 	}
  39.  
  40. 	for(int i=1;i<N;i++){
  41. 		if( arr[i]==0 ){
  42. 			for(int j=1;j<=M;j++)
  43. 				add(i,j);
  44. 		}
  45. 		else add(i,arr[i]);
  46. 	}
  47. 	ll ans=0;
  48. 	for(int j=1;j<=M;j++){
  49. 		ans+=dp[N-1][j];
  50. 		ans%=mod;
  51. 	}
  52. 	cout<<ans;
  53. }
Success #stdin #stdout 0.01s 5672KB
comments (?)
stdin 
3 5
2 0 2
stdout 
3
https://ideone.com/l1lRcE
CSES-Array Description
language:
C++14 (gcc 8.3)
created:
2 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!