#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
int n;
cin>>n;
vl a(n + 1);
for (int i = 1;i<=n;i++)cin>>a[i];
vvl dp(n + 1,vl(n + 1));
ll ans = 0;
ll mx = 0;
for (int i = n;i>=1;i--){
for (int j = n;j>=1;j--){
if (i == n){dp[i][j] = min(1ll * n,1ll * j + 1);continue;}
if (i < j)continue;
dp[i][j] = (1ll * j * (dp[i + 1][j]))%mod;
if (j != n)dp[i][j] = (dp[i][j] + dp[i + 1][j + 1])%mod;
}
}
for (int i = 1;i<=n;i++){
if (i != n){
for (int j = 1;j<a[i];j++){
ans = (ans + dp[i + 1][max(mx,1ll * j)])%mod;
}
}
else
ans = (ans + a[i])%mod;
mx = max(mx,a[i]);
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
8160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
46 ms |
65540 KB |
Execution killed with signal 9 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
39 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
39 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |