Submission #755914

#	Time	Username	Problem	Language	Result	Execution time	Memory
755914		vjudge1	A Huge Tower (CEOI10_tower)	C++17	40 / 100	1082 ms	262148 KiB

tower

#include <bits/stdc++.h>

        using namespace std;
        using ll = long long;

        #define int ll

        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);
                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);
                res %= MOD;
            }
            cout << res % MOD << "\n";
        }

• 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: 0 / 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