Submission #1121867

#TimeUsernameProblemLanguageResultExecution timeMemory
1121867raul2008487Calvinball championship (CEOI15_teams)C++17
70 / 100
46 ms16880 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define in insert #define fi first #define se second #define vl vector<ll> #define all(v) v.begin(), v.end() #define endl "\n" using namespace std; const int sz = 1e3 + 5; /// mind this const int MAX = 2e6 + 123; const int BS = 61; const int mod = 1e6 + 7; ll dp[sz][sz]; ll bp(ll a, ll b){ ll res = 1; a %= mod; while(b){ if(b & 1){ res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } void solve(){ ll n, i, j, hi = 0, ans = 1; cin >> n; vl v(n + 1), fp(n + 1, -1); dp[0][0] = 1; for(i = 1; i <= n; i++){ cin >> v[i]; hi = max(hi, v[i]); dp[0][i] = 1; } for(i = 1; i <= n; i ++){ // cout << i << ": "; for(j = 0; j <= n - i; j++){ dp[i][j] = (dp[i - 1][j + 1] + (dp[i - 1][j] * j) % mod) % mod; // cout << dp[i][j] << ' '; } // cout << endl; } ll mx = 0; for(i = 1; i <= n; i++){ for(j = 1; j < v[i]; j++){ ans = (ans + dp[n - i][max(mx, j)]) % mod; } mx = max(mx, v[i]); } cout << ans<< endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t = 1; // cin >> t; while(t--){ solve(); } } /* 3 1 2 2 */
#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...