Submission #1315665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315665		thesimpleone	A Huge Tower (CEOI10_tower)	C++20	45 / 100	363 ms	327680 KiB

tower

///   ***   ---   |||   In the name of ALLAH   |||   ---   ***   ///

#include <bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define MOD 1000000009

int main() {
    fastio();

    int n;
    ll d;
    cin >> n >> d;

    vector<ll> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    int mx = 1 << n;   // safe because n <= 20
    vector<vector<ll>> dp(mx, vector<ll>(n, 0));

    // Base case: one block as bottom
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = 1;
    }

    // Bitmask DP
    for (int mask = 0; mask < mx; mask++) {
        for (int last = 0; last < n; last++) {

            // last must be used
            if ((mask & (1 << last)) == 0) continue;
            if (dp[mask][last] == 0) continue;

            for (int nxt = 0; nxt < n; nxt++) {

                // nxt must be unused
                if ((mask & (1 << nxt)) != 0) continue;

                // size constraint
                if (h[nxt] <= h[last] + d) {
                    int newMask = mask | (1 << nxt);
                    dp[newMask][nxt] =
                        (dp[newMask][nxt] + dp[mask][last]) % MOD;
                }
            }
        }
    }

    // Collect answer
    ll ans = 0;
    int fullMask = mx - 1;
    for (int i = 0; i < n; i++) {
        ans = (ans + dp[fullMask][i]) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5