Submission #527228

#TimeUsernameProblemLanguageResultExecution timeMemory
527228joelauCalvinball championship (CEOI15_teams)C++14
100 / 100
413 ms656 KiB
#include <bits/stdc++.h> using namespace std; long long N, A[10005], dp[2][10005], most[10005], p = 1000007; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N; most[0] = 0; for (long long i = 1; i <= N; ++i) { cin >> A[i]; most[i] = max(most[i-1],A[i]); } for (long long i = 1; i <= N+1; ++i) dp[1][i] = 1; long long ans = 1; for (long long i = N; i > 0; --i) { for (long long j = 1; j <= i; ++j) dp[0][j] = (dp[1][j] * j + dp[1][j+1]) % p; ans = (ans + dp[1][most[i-1]] * min(most[i-1],A[i]-1)) % p; for (long long j = most[i-1]+1; j < A[i]; ++j) ans = (ans + dp[1][j]) % p; swap(dp[0],dp[1]); } cout << ans; 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...