Submission #755918

#TimeUsernameProblemLanguageResultExecution timeMemory
755918MohamedFaresNebiliA Huge Tower (CEOI10_tower)C++14
45 / 100
963 ms208480 KiB
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 9; int N, D, A[100], DP[(1 << 20) + 5][25]; int solve(int mask, int last) { if(__builtin_popcount(mask) == N) return 1; if(DP[mask][last] != -1) return DP[mask][last]; int res = 0; for(int l = 0; l < N; l++) { if(mask & (1 << l)) continue; if(A[l] > D + A[last]) continue; res += (solve(mask | (1 << l), l)) % MOD; res %= MOD; } return DP[mask][last] = res % MOD; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> D; memset(DP, -1, sizeof DP); for(int l = 0; l < N; l++) cin >> A[l]; int res = 0; for(int l = 0; l < N; l++) { res += (solve((1 << l), l)) % MOD; res %= MOD; } cout << res % MOD << "\n"; }
#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...