#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,avx,mmx,popcnt,tune=native")
using namespace std;
const int mod = 1e9 + 7;
int n, dp[2][10002][2], p[10002];
void add (int &a, int b) {
a += b;
if (a >= mod)
a-= mod;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i];
dp[0][0][1] = 1;
for (int i = 0; i < n; i++) {
int k = (i & 1);
for (int j = 0; j <= n; j++)
dp[k ^ 1][j][0] = dp[k ^ 1][j][1] = 0;
for (int j = 0; j <= n; j++) {
///1 lmao
if (j > 0)
add(dp[k ^ 1][j][1], dp[k][j][1] * (p[i + 1] <= j));
if (j < n)
add(dp[k ^ 1][j + 1][1], dp[k][j][1] * (j + 1 == p[i + 1]));
///0 lmao
if (j > 0) {
add(dp[k ^ 1][j][0], dp[k][j][1] * min(j, p[i + 1] - 1) % mod);
add(dp[k ^ 1][j][0], dp[k][j][0] * j % mod);
}
if (j < n) {
add(dp[k ^ 1][j + 1][0], dp[k][j][1] * (j + 1 < p[i + 1]));
add(dp[k ^ 1][j + 1][0], dp[k][j][0]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
add(ans, dp[n ^ 1][i][0]);
add(ans, dp[n ^ 1][i][1]);
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
408 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
488 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
995 ms |
808 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
253 ms |
588 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1018 ms |
788 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |