Submission #527101

#TimeUsernameProblemLanguageResultExecution timeMemory
527101zaneyuCalvinball championship (CEOI15_teams)C++14
10 / 100
24 ms23628 KiB
/*input 3 1 2 2 */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; //#pragma GCC optimize("unroll-loops,no-stack-protector") //order_of_key #of elements less than x // find_by_order kth element using ll = long long; using ld = long double; using pii = pair<ll,ll>; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; #define f first #define s second #define pb push_back #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define FILL(n,x) memset(n,x,sizeof(n)) #define ALL(_a) _a.begin(),_a.end() #define sz(x) (int)x.size() #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #define MP make_pair const ll INF64=4e17; const int INF=0x3f3f3f3f; const ll MOD=1e6+7; const ld PI=acos(-1); const ld eps=1e-9; #define lowb(x) x&(-x) #define MNTO(x,y) x=min(x,(__typeof__(x))y) #define MXTO(x,y) x=max(x,(__typeof__(x))y) template<typename T1,typename T2> ostream& operator<<(ostream& out,pair<T1,T2> P){ out<<P.f<<' '<<P.s; return out; } template<typename T> ostream& operator<<(ostream& out,vector<T> V){ REP(i,sz(V)) out<<V[i]+1<<((i!=sz(V)-1)?" ":""); return out; } ll mult(ll a,ll b){ return ((a%MOD)*(b%MOD))%MOD; } ll mypow(ll a,ll b){ if(b<=0) return 1; ll res=1LL; while(b){ if(b&1) res=mult(res,a); a=mult(a,a); b>>=1; } return res; } const int maxn=1e3+5; ll dp[maxn][maxn][2]; int arr[maxn]; int main(){ int n; cin>>n; REP1(i,n) cin>>arr[i]; dp[0][0][1]=1; REP1(i,n){ REP1(j,arr[i]){ if(j==arr[i]){ dp[i][j][1]=dp[i-1][j][1]+dp[i-1][j-1][1]; dp[i][j][0]=dp[i-1][j][0]*j+dp[i-1][j][1]*(j-1)+dp[i-1][j-1][0]; } else{ dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])*j+(dp[i-1][j-1][0]+dp[i-1][j-1][1]); } REP(k,2) dp[i][j][k]%=MOD; } } ll ans=1; REP1(j,arr[n]) ans+=dp[n][j][0],ans%=MOD; cout<<ans; }
#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...