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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mod = 1e6 + 7, Nmax = 10005;
int n, i, now, old, C;
int mx[Nmax], a[Nmax], dp[2][Nmax];
ll ans = 1;
void advance_dp()
{
swap(now, old);
int i;
for(i=0; i<=n; ++i)
dp[now][i] = ( (ll) dp[old][i] * i + dp[old][i+1] ) % Mod;
}
void init_dp()
{
now = 0, old = 1;
int i;
for(i=0; i<=n; ++i)
dp[now][i] = 1;
}
int main()
{
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
cin.sync_with_stdio(false);
cin >> n;
for(i=1; i<=n; ++i)
{
cin >> a[i];
mx[i] = max(mx[i-1], a[i]);
}
init_dp();
for(i=n; i; --i)
{
C = mx[i-1];
ans += (ll) dp[now][C] * (a[i] - 1);
ans %= Mod;
advance_dp();
}
cout << ans << '\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... |