Submission #555403

#TimeUsernameProblemLanguageResultExecution timeMemory
555403hidden1Calvinball championship (CEOI15_teams)C++14
20 / 100
953 ms696 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #ifndef LOCAL #define cerr if(false) cerr #endif #define endl "\n" #define out(x) "[" << #x << "=" << x << "]" struct debug { debug() { cerr << "DEBUGGER: " << endl; } ~debug() { cerr << endl << "DEBUGGER_END " << endl; } template<class T> debug& operator <<(const T x) { cerr << x << " "; return *this; } }; template<class T> inline ostream &operator <<(ostream &out, const vector<T> &x) { for(const auto &it : x) { out << it << " "; } return out; } template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { return out << x.first << " " << x.second; } template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } typedef long long ll; const ll mod = 1e9 + 7; //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// const ll MAX_N = 2e4 + 10; ll dp[2][MAX_N]; ll n; ll arr[MAX_N]; signed main() { #ifndef LOCAL ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #endif cin >> n; for(ll i = 1; i <= n; i ++) { cin >> arr[i]; } ll mx = 0; for(ll i = 0; i < n; i ++) { ll curr = i & 1; ll nxt = curr ^ 1; for(ll j = 0; j < MAX_N; j ++) { dp[nxt][j] = 0; } for(ll j = 0; j < MAX_N - 1; j ++) { dp[nxt][j] += (dp[curr][j] * j) % mod; dp[nxt][j] %= mod; dp[nxt][j + 1] += dp[curr][j]; dp[nxt][j + 1] %= mod; } assert(mx + 1 == arr[i + 1] || mx >= arr[i + 1]); dp[nxt][mx] += arr[i + 1] - 1; dp[nxt][mx] %= mod; chkmax(mx, arr[i + 1]); continue; cout << i << endl; for(ll i = 0; i <= n; i ++) { cout << dp[curr][i] << " "; } cout << endl; } ll ret = 1; for(ll i = 0; i < MAX_N; i ++) { ret = (ret + dp[n & 1][i]) % mod; } cout << ret << 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...