Submission #146741

#TimeUsernameProblemLanguageResultExecution timeMemory
146741vexCalvinball championship (CEOI15_teams)C++14
100 / 100
133 ms732 KiB
#include<bits/stdc++.h> #define maxn 10005 #define mod 1000007 #define ll long long using namespace std; int n; int a[maxn]; ll dp[2][maxn]; int g[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; g[1]=1; for(int i=2;i<=n;i++)g[i]=max(g[i-1],a[i]); /*for(int d=1;d<n;d++) { for(int k=1;k+d<=n;k++) { if(d==1)dp[d][k]=k+1; else { dp[d][k]=dp[d-1][k+1]+k*dp[d-1][k]; dp[d][k]%=mod; } } }*/ /*for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<dp[i][j]<<" "; } cout<<endl; }*/ int prev=0; int curr=1; long long ans=0; for(int i=n;i>=2;i--) { if(i!=n) { int d=n-i; for(int k=1;k+d<=n;k++) { if(d==1)dp[curr][k]=k+1; else { dp[curr][k]=dp[prev][k+1]+k*dp[prev][k]; dp[curr][k]%=mod; } } } ll br; if(i==n) { br=1; } else if(g[i]==g[i-1]) { br=dp[curr][g[i]]; } else { br=dp[curr][g[i]-1]; } ans+=(a[i]-1)*br; ans%=mod; swap(curr,prev); } cout<<(ans+1)%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...