Submission #958864

#TimeUsernameProblemLanguageResultExecution timeMemory
958864GhettoCalvinball championship (CEOI15_teams)C++17
20 / 100
39 ms65536 KiB
#include <bits/stdc++.h> using namespace std; using lint = long long; const int MAX_N = 1e4 + 5; const lint MOD = 1e9 + 7; int n; int arr[MAX_N]; lint mod(lint x) { return x % MOD; } lint dp[MAX_N][MAX_N]; void precomp() { for (int s = n; s >= 1; s--) { for (int t = 1; t <= s; t++) { if (s == n) dp[s][t] = 1; else dp[s][t] = mod(dp[s + 1][t + 1] + mod(t * dp[s + 1][t])); } } } int main() { // freopen("calvin.in", "r", stdin); cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; precomp(); set<int> unis; lint ans = 0; for (int i = 1; i <= n; i++) { lint n_unis = unis.size(); ans = mod(ans + mod(dp[i][n_unis] * (arr[i] - 1))); // Should be fine if n_unis = 0 unis.insert(arr[i]); } ans++; 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...