#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 10'010;
const int mod = 1e9+7;
ll dp[2][N];
ll dp_lte[2][N];
int a[N];
int n;
void update_dp(int i)
{
int i2 = i&1;
Loop (mx_st,0,N-1) {
dp[i2][mx_st] = mx_st*dp[!i2][mx_st] + dp[!i2][mx_st+1];
if (mx_st < a[i])
dp_lte[i2][mx_st] = dp[i2][mx_st];
else if (mx_st == a[i])
dp_lte[i2][mx_st] = mx_st*dp[!i2][mx_st] + dp_lte[!i2][mx_st+1];
else /* mx_st > a[i] */
dp_lte[i2][mx_st] = a[i]*dp[!i2][mx_st] + dp_lte[!i2][mx_st];
dp[i2][mx_st] %= mod;
dp_lte[i2][mx_st] %= mod;
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop (i,0,n) {
cin >> a[i];
--a[i];
}
Loop (i,0,N)
dp[n&1][i] = dp_lte[n&1][i] = 1;
LoopR (i,0,n)
update_dp(i);
cout << dp_lte[0][0] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
584 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
580 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
584 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
41 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
453 ms |
744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
221 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
410 ms |
688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |