Submission #755985

#TimeUsernameProblemLanguageResultExecution timeMemory
755985vjudge1A Huge Tower (CEOI10_tower)C++17
45 / 100
1079 ms262144 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; const ll MOD = 1e9 + 9; ll mod(ll x, ll m = MOD){return (x + m) % m;} typedef vector<int> vi; typedef vector<ll> vll; typedef pair<ll,ll> pll; typedef vector<pair<int,int>> vpi; #define pb push_back #define ff first #define ss second #define all(x) (x).begin(),(x).end() const int nax = 504; const int bnax = 20; int n, d; vi A; ll dp[bnax][(1 << bnax)]; int pos[(1 << bnax)]; int go[bnax]; int LSOne(int val) { return pos[val & (- val)] ; } ll f(int i, int mask) { if(dp[i][mask] != -1) return dp[i][mask]; if(mask == (1 << n) - 1) return dp[i][mask] = 1ll; ll ans = 0ll; int rem = (((1 << n) - 1) - mask) & go[i]; for(int j = LSOne(rem); rem > 0; j = LSOne(rem)) { ans = mod(ans + f(j, mask + (1 << j))); rem -= (1 << j); } return dp[i][mask] = ans; } void solve() { memset(dp, -1, sizeof(dp)); cin >> n >> d; A.resize(n); for(int i = 0; i < n; i++) cin >> A[i]; ll ans = 0ll; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(A[j] <= A[i] + d) go[i] += (1 << j); } } for(int i = 0; i < n; i++) { ans = mod(ans + f(i, (1 << i))); } cout << ans; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; for(int i = 0; i < 20 ;i++) pos[(1 << i)] = i; while(tt--) solve(); }
#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...