This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <fstream>
#include <bitset>
#include <cassert>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); i++)
#define INF 1145141919
#define MOD 1000007
#define pb push_back
using namespace std;
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }
int N;
int A[10000];
int dp[2][10000];
signed main() {
cin >> N;
rep(i, N) cin >> A[i], A[i]--;
int lm = 0;
for (int i=1; i<N; i++) {
rep(s, i+1) dp[1][s] = 0;
rep(s, i+1) {
add(dp[1][s], (1LL*(s+1)*dp[0][s])%MOD);
add(dp[1][s+1], dp[0][s]);
}
add(dp[1][lm], A[i]);
if (A[i] == lm+1) lm++;
swap(dp[0], dp[1]);
}
int s = 0;
rep(i, N) add(s, dp[0][i]);
cout << s+1 << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |