Submission #898663

#TimeUsernameProblemLanguageResultExecution timeMemory
898663math_rabbit_1028Fibonacci representations (CEOI18_fib)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll MOD = 1e9 + 7; int n, arr[101010]; int 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++) { int d = arr[i] - arr[i - 1]; if (d % 2 == 0) dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] - 1 + MOD) % MOD; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (d/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...