#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int MOD = 1000007;
int add(int x, int y) {
return x + y < MOD ? x + y : x + y - MOD;
}
int mul(int x, int y) {
return (ll)x * y % MOD;
}
const int N = 10500;
int a[N], b[N];
int n;
int dp[2][N];
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
b[0] = 0;
for (int i = 1; i < n; i++)
b[i] = max(b[i - 1], a[i - 1]);
for (int v = 1; v <= n; v++)
dp[n & 1][v] = 1;
int ans = 1;
for (int i = n - 1; i >= 0; i--) {
for (int v = 1; v < a[i]; v++) {
ans = add(ans, dp[(i + 1) & 1][max(b[i], v)]);
}
for (int v = 1; v <= n; v++)
dp[i & 1][v] = 0;
for (int v = 1; v <= n; v++) {
dp[i & 1][v] = add(dp[(i + 1) & 1][v + 1], mul(v, dp[(i + 1) & 1][v]));
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
teams.cpp: In function 'int main()':
teams.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
teams.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
268 KB |
Output is correct |
2 |
Correct |
2 ms |
312 KB |
Output is correct |
3 |
Correct |
2 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
366 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
68 ms |
396 KB |
Output is correct |
2 |
Correct |
68 ms |
396 KB |
Output is correct |
3 |
Correct |
92 ms |
400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
271 ms |
492 KB |
Output is correct |
2 |
Correct |
280 ms |
480 KB |
Output is correct |
3 |
Correct |
367 ms |
452 KB |
Output is correct |