# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
221872 | PeppaPig | Calvinball championship (CEOI15_teams) | C++14 | 369 ms | 760 KiB |
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>
#define long long long
using namespace std;
const int N = 1e4+5;
const int M = 1e6+7;
int n, A[N], mx[N];
long dp[2][N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", A + i);
mx[i] = max(mx[i - 1], A[i]), dp[0][i] = 1;
}
long ans = 1ll * (A[n] - 1) * dp[0][mx[n - 1]];
for(int i = 1; i <= n; i++) {
int now = i & 1, pre = now ^ 1;
for(int j = 0; j <= n; j++)
dp[now][j] = (1ll * j * dp[pre][j] % M + dp[pre][j + 1]) % M;
if(i < n)
ans = (ans + (A[n - i] - 1) * dp[now][mx[n - i - 1]]) % M;
}
printf("%lld\n", ans + 1);
return 0;
}
Compilation message (stderr)
# | 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... |