Submission #364801

#TimeUsernameProblemLanguageResultExecution timeMemory
364801knightron0Calvinball championship (CEOI15_teams)C++14
100 / 100
837 ms748 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fr first #define sc second #define clr(a, x) memset(a, x, sizeof(a)) #define dbg(x) cout<<"("<<#x<<"): "<<x<<endl; #define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl; #define all(v) v.begin(), v.end() #define lcm(a, b) (a * b)/__gcd(a, b) #define int long long int #define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl; #define endl '\n' #define float long double const int MOD = 1e6 + 7; const int INF = 2e15; const int MAXN = 1e5 + 5; int fastexpo(int b, int exp){ if(exp == 0) return 1; if(exp == 1) return b; int ans = (fastexpo(b,exp/2) % MOD); ans *= ans; ans %= MOD; if(exp % 2 == 1){ ans *= b; } ans %= MOD; return ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif int n; cin>>n; int a[n+1]; int prefmx[n+2]; prefmx[0] = 0; for(int i=1;i<=n;i++){ cin>>a[i]; prefmx[i] = prefmx[i-1]; prefmx[i] = max(prefmx[i], a[i]); } int dp[2][n+2]; for(int j=1;j<=n;j++) dp[0][j]= 1; int ans = a[n]%MOD; for(int i= 1;i<n;i++){ int par = (i%2); for(int j= 1;j<=n;j++){ dp[par][j] = (((dp[par^1][j]%MOD)*(j%MOD))%MOD + (dp[par^1][j+1]%MOD))%MOD; } ans +=((dp[par][prefmx[n-i-1]]%MOD)*(a[n-i]-1+MOD)%MOD)%MOD; ans %= MOD; } cout<<ans%MOD<<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...