# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
65320 | 2018-08-07T11:29:37 Z | bazsi700 | Calvinball championship (CEOI15_teams) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define MOD 1000007 #define ll long long int ll dp[10005]; //ll dp2[10005]; ll calc() { for(int i = 1; i <= 10000; i++) { dp[i] = (dp[i+1]+dp[i]*i); } /*for(int i = 1; i <= 10000; i++) { dp[i] = dp2[i]; }*/ } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> arr(n); vector<int> cnt(n+1,0); for(int i = 0; i < n; i++) { dp[i] = 1; cin >> arr[i]; cnt[arr[i]]++; } dp[n] = 1; ll ans = 1; for(int i = n-1; i >= 0; i--) { if(arr[i] > 1) { if(cnt[arr[i]] == 1) { ans+= ((arr[i]-1)*dp[arr[i]-1]); } else { ans+= ((arr[i]-1)*dp[arr[i]]); } calc(); cnt[arr[i]]--; } cout << ans; return 0; }