Submission #1011197

#TimeUsernameProblemLanguageResultExecution timeMemory
1011197gygCalvinball championship (CEOI15_teams)C++17
40 / 100
278 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 1e4 + 5, MOD = 1e6 + 7; int n; array<int, MAX_N> a; array<bool, MAX_N> is_first; void precomp() { int max_val = 0; for (int i = 1; i <= n; i++) { if (a[i] <= max_val) continue; max_val = a[i], is_first[i] = true; } } array<array<int, MAX_N>, 2> dp; int comp() { auto mod = [](int x) { return (x + MOD) % MOD; }; int ans = 0; for (int s = 0; s < n; s++) { int p = s % 2, opp_p = (s + 1) % 2; for (int c = 1; c <= n + 1; c++) { if (s == 0) { dp[p][c] = 1; continue; } int leave = mod(dp[opp_p][c] * c); int take = dp[opp_p][c + 1]; dp[p][c] = mod(leave + take); } int i = n - s, new_ans = 0; if (is_first[i]) new_ans = mod((a[i] - 1) * dp[p][a[i] - 1]); else new_ans = mod((a[i] - 1) * dp[p][a[i]]); ans = mod(ans + new_ans); } ans = mod(ans + 1); return ans; } signed main() { // freopen("teams.in", "r", stdin); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; precomp(); int ans = comp(); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...