Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for(int i = a; i < b; ++i)
  5. #define REP(i, n) FOR(i, 0, n)
  6. #define _ << " " <<
  7. #define sz(x) ((int) x.size())
  8. #define pb(x) push_back(x)
  9. #define TRACE(x) cerr << #x << " = " << x << endl
  10.  
  11. typedef long long ll;
  12. typedef pair<int, int> point;
  13.  
  14. const int mod = 1e9 + 7;
  15.  
  16. int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
  17. int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
  18. int mul(int x, int y) {return (ll) x * y % mod;}
  19.  
  20. const int MAXN = 505;
  21.  
  22. int n, a[MAXN], dp[MAXN][MAXN];
  23.  
  24. int main(){
  25.   ios_base::sync_with_stdio(false); cin.tie(0);
  26.  
  27.   cin >> n;
  28.   REP(i, n)
  29.     cin >> a[i];
  30.  
  31.   if(a[0] != 0){
  32.     cout << 0;
  33.     return 0;
  34.   }
  35.  
  36.   dp[0][0] = 1;
  37.   FOR(i, 1, n){
  38.     int mx = min(i, n - 1 - i);
  39.     FOR(j, 0, n){
  40.       if(j > mx) continue;
  41.       if(a[i] != -1 && j != a[i]) continue;
  42.  
  43.       if(j > 0)
  44.         dp[i][j] = add(dp[i][j], dp[i - 1][j - 1]);
  45.       dp[i][j] = add(dp[i][j], dp[i - 1][j]);
  46.       dp[i][j] = add(dp[i][j], dp[i - 1][j + 1]);
  47.     }
  48.   }
  49.   cout << dp[n - 1][0];
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement