Submission #898672

#TimeUsernameProblemLanguageResultExecution timeMemory
898672math_rabbit_1028Fibonacci representations (CEOI18_fib)C++14
15 / 100
4083 ms2116 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll MOD = 1e9 + 7; int n, arr[101010]; ll dp[101010][2]; void solve(vector<int> vec) { sort(vec.begin(), vec.end()); int k = vec.size(); for (int i = 0; i < k; i++) dp[i][0] = dp[i][1] = 0; dp[0][0] = 1; dp[0][1] = (vec[0] - 1) / 2; for (int i = 1; i < k; i++) { ll d = vec[i] - vec[i - 1]; ll v = i == 1 ? 1 : (dp[i-2][0] + dp[i-2][1]) % MOD; if (d % 2 == 0) dp[i][0] = (dp[i-1][0] + dp[i-1][1] - v + MOD) % MOD; dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD * ((d+1)/2) % MOD; } cout << (dp[k-1][0] + dp[k-1][1]) % MOD << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; vector<int> vec; for (int i = 1; i <= n; i++) { vec.push_back(arr[i]); solve(vec); } 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...