Submission #590504

#TimeUsernameProblemLanguageResultExecution timeMemory
590504nodal_treeA Huge Tower (CEOI10_tower)C++17
15 / 100
303 ms7548 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 9; int main() { int N; int D; cin >> N >> D; int dp[N + 1]; int top[N + 1]; int a[N + 1]; a[0] = 0; dp[0] = 1; top[0] = 0; for(int i = 1; i<=N; i++){ cin >> a[i]; dp[i] = 1; top[i] = 0; } sort(a, a + N); int l = 1; for(int r = 1; r<=N; r++){ while(a[r] - a[l] > D){ l++; } top[r] = r - l; } for(int i = 1; i<=N; i++){ dp[i] = (dp[i - 1] * 1LL * (top[i] + 1)) % MOD; } cout << dp[N] << '\n'; 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...
#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...