#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e4+5, mod = 1e6 + 7;
//const int maxn = 5, mod = 1e6 + 7;
inline void upd(int &a, const int &b)
{
a += b;
if (a >= mod) a-= b;
}
inline int mul(const int &a, const int &b)
{
return (1ll * a * b) % (ll)(mod);
}
inline int add(const int &a, const int &b)
{
int c = a + b;
if (c >= mod) c -= mod;
return c;
}
int dp[2][maxn][2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
dp[0][0][1] = 1;
for (int i = 0, x; i < n; i++)
{
cin >> x;
int nw = ((i+1)&1), pv = (i&1);
memset(dp[nw], 0, sizeof(dp[nw]));
for (int t = 0; t <= i; t++) for (int fw = 0; fw < 2; fw++) if (dp[pv][t][fw])
{
int join = t;
if (fw)
{
join = min(join, x-1);
if (t >= x) upd(dp[nw][t][fw], dp[pv][t][fw]); // patrim do timu x
}
upd(dp[nw][t][fw], mul(dp[pv][t][fw], join));
if (!fw || x >= t+1)
{
upd(dp[nw][t+1][fw&(x == t+1)], dp[pv][t][fw]);
}
}
}
int ans = 0;
for (int t = 0; t <= n; t++) for (int fw = 0; fw < 2; fw++) upd(ans, dp[n&1][t][fw]);
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
440 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
574 ms |
492 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
106 ms |
464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
387 ms |
480 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |