# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54828 | 2018-07-05T07:51:35 Z | 윤교준(#1510) | Calvinball championship (CEOI15_teams) | C++11 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define befv(V) ((V)[sz(V)-2]) #define sorv(V) sort(allv(V)) #define revv(V) reverse(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define upmax(a,b) (a)=max((a),(b)) #define upmin(a,b) (a)=min((a),(b)) #define rb(x) ((x)&(-(x))) #define INF (0x3f3f3f3f) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 10005; const int MOD = 1000007; int dp[MAXN][MAXN]; int A[MAXN]; int Ans; int N; int main() { freopen("input.txt", "r", stdin); ios::sync_with_stdio(false); cin >> N; for(int i = 1; i <= N; i++) cin >> A[i]; for(int i = 1; i <= N; i++) dp[0][i] = 1; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) dp[i][j] = (ll(dp[i-1][j]) * j + dp[i-1][j+1]) % MOD; for(int i = 2, mx = 1; i <= N; i++) { if(1 == A[i]) continue; Ans = (f(N-i, mx) * (A[i]-1) + Ans) % MOD; upmax(mx, A[i]); } Ans++; cout << (((Ans % MOD) + MOD) % MOD) << endl; return 0; }