Submission #86280

#TimeUsernameProblemLanguageResultExecution timeMemory
86280rzbtCalvinball championship (CEOI15_teams)C++14
100 / 100
417 ms1068 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 10010; const ll MOD = 1000007LL; ll dp[2][MAXN]; ll tot; int N,vetor[MAXN]; ll solve(int pos,int maior){ if(dp[pos][maior] != -1) return dp[pos][maior]; if(pos == N + 1){ return dp[pos][maior] = 1; } ll ans = 1LL*(maior - 1)*solve(pos+1,maior); ans += solve(pos+1,maior+1); return dp[pos][maior] = (int)(ans % MOD); } int main(){ cin >> N; for(int i = 1;i<=N;i++) cin >> vetor[i]; for(int i = 1;i<=N+2;i++) dp[0][i] = 1; for(int i = N;i>=1;i--){ int maior = 0; for(int j = 1;j<i;j++) maior = max(maior,vetor[j]); swap(dp[0],dp[1]); for(int j = 1;j<=N+1;j++){ dp[0][j] = (j-1)*dp[1][j] + dp[1][j+1]; dp[0][j] %= MOD; } for(int j = 1;j<vetor[i];j++){ tot += dp[1][max(j,maior) + 1]; } tot %= MOD; } tot++; tot %= MOD; cout << tot << endl; return 0; }
#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...