Submission #1262849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262849		nimoxide	A Huge Tower (CEOI10_tower)	C++20	20 / 100	411 ms	78504 KiB

tower

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

const int MAXN = 100;
const long long MOD = 1e9 + 7;

int n, d, a[MAXN];
long long dp[30][1 << 20], answer;
vector<int> graph[MAXN];

void input();
void generateGraph();
void countLenNP();

int main() {
	input();
	generateGraph();
	countLenNP();
	cout << answer % MOD << endl;
}

void input() {
	cin >> n >> d;
	for (int i = 0; i < n; i++)
		cin >> a[i];
}

void generateGraph() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (a[i] - a[j] >= -d)
				graph[i].push_back(j);
}

void countLenNP() {
    for (int v = 0; v < n; v++)
		dp[v][1 << v] = 1;

    for (int mask = 1; mask < (1 << n); mask++) 
        for (int v = 0; v < n; v++) {
            if (!(mask & (1 << v))) 
				continue;
            for (int u : graph[v]) {
                if (mask & (1 << u)) 
					continue;
                dp[u][mask | (1 << u)] += dp[v][mask] % MOD;
                dp[u][mask] %= MOD;
        	}
        }
	
    for (int mask = 1; mask < (1 << n); mask++) 
        if (__builtin_popcount(mask) == n) 
            for (int v = 0; v < n; v++) {
                answer += dp[v][mask];
            	answer %= MOD;
			}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 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