Submission #1164849

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

#define MAX 2010

ll mod = 1000000007;

int N,A[MAX], pre[MAX],nex[MAX];
long long dp[MAX][2100];

void compute() {
  nex[0] = A[0], nex[N-1] = A[N-1];
  pre[0] = A[0], pre[N-1] = A[N-1];
  for(int i=N-2;i>=1;--i) {
    if( A[i] == -1 ) nex[i] = nex[i+1];
    else             nex[i] = A[i];
  }
  REP(i,1,N-1) {
    if( A[i] != -1 ) pre[i] = A[i];
    else             pre[i] = pre[i-1];
  }

  dp[0][A[0]] = 1;
  REP(i,1,N) {
    REP(j,1,nex[i]+1) {
      dp[i][j] = ( dp[i][j-1] + dp[i-1][j] ) % mod;
    }
    rep(j,pre[i]) dp[i][j] = 0;
  }
  cout << dp[N-1][A[N-1]] << endl;
}

int main() {
  cin >> N;
  rep(i,N) cin >> A[i];
  compute();
  return 0;
}

Submission Info

Judge Result