fork download
copy 
  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 N = 1e6 + 5;
  9. const int mod = 1e9 + 7;
  10.  
  11. int n, m;
  12. int a[N], sum[N], dp[N];
  13.  
  14. inline int add(int x, int y) {
  15. 	return x + y >= mod ? x + y - mod : x + y;
  16. }
  17.  
  18. int main() {
  19.  
  20. 	scanf("%d %d", &n, &m);
  21.  
  22. 	assert(n <= 50);
  23.  
  24. 	for(int i = 1; i <= m; i++) {
  25. 		int x;
  26. 		scanf("%d", &x);
  27. 		a[x]++;
  28. 	}
  29.  
  30. 	for(int i = 1; i <= n; i++)
  31. 		sum[i] = sum[i - 1] + a[i];
  32.  
  33. 	dp[n + 1] = 1;
  34. 	dp[n + 2] = 1;
  35.  
  36. 	for(int i = n; i >= 1; i--) {
  37. 		if(!a[i-1])
  38. 		for(int j = i; j <= n; j++) {
  39. 			if(j - i + 1 == sum[j] - sum[i - 1] and !a[j + 1]) {
  40. 				for(int k = j + 2; k <= n + 2; k++) {
  41. 					dp[i] = add(dp[i], dp[k]);
  42. 					if(a[k] or k == n + 1)
  43. 						break;
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	int ans = 0;
  50.  
  51. 	for(int i = 1; i <= n + 1; i++) {
  52. 		ans = add(ans, dp[i]);
  53. 		if(a[i])
  54. 			break;
  55. 	}
  56.  
  57. 	printf("%d\n", ans);
  58.  
  59.     return 0;
  60.  
  61. }
  62.  
  63.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/fM5nVp
language:
C++14 (clang 8.0)
created:
5 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!