Submission #43992

#TimeUsernameProblemLanguageResultExecution timeMemory
43992sorry_BenqCalvinball championship (CEOI15_teams)C++17
100 / 100
132 ms1104 KiB
#include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int MOD = 1e6 + 7; ll a[10005]; ll DP[10005]; ll mxs[10005]; /*int solve(int N, int K){ //you have N numbers left, and they can start anywhere from 1 - K. if (DP[N][K] != 0) return DP[N][K]; if (N == 0) return 1; else{ return DP[N][K] = (((long long) K)*solve(N - 1, K) + solve(N - 1, K + 1))%MOD; } }*/ int cnt = 10005; void evolve(){ for (int i = 0; i < cnt - 1; i++){ DP[i] = ((long long) i)*DP[i] + DP[i + 1]; DP[i] %= MOD; } cnt--; } main(){ int N; cin >> N; for (int i = 0; i < N; i++){ cin >> a[i]; } for (int i = 0; i < cnt; i++){ DP[i] = 1; } ll res = 1; int mx = 1; for (int i = 0; i < N; i++){ mxs[i] = mx; mx = max(mx, a[i]); } for (int i = N - 1; i >= 0; i--){ //matches prefix of length i res += ((ll) a[i] - 1)*DP[mxs[i]]; evolve(); res %= MOD; } cout << res << endl; }

Compilation message (stderr)

teams.cpp:31:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#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...