Submission #332630

#	Time	Username	Problem	Language	Result	Execution time	Memory
332630		8e7	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	1542 ms	78956 KiB

skyscraper

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#define ll long long
#define maxn 100005
#define mod 1000000007
#define zckorz ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int dp[105][14][1<<14];
int ab[14][14];
int main() {
	zckorz
	int n, l;
	cin >> n >> l;
	int a[n];
	for (int i = 0;i < n;i++) cin >> a[i];
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) ab[i][j] = max(a[i] - a[j], a[j] - a[i]);
	}
	for (int i = 0;i < n;i++) dp[0][i][1<<i] = 1;
	for (int bit = 1;bit < (1<<n);bit++) {
		if (bit - (bit & (-bit)) == 0) continue;
		//cout << bit << endl;
		for (int i = 0;i < n;i++) {
			if (bit & (1<<i)) {
				int rem = bit - (1<<i);
				for (int tot = 0;tot <= l;tot++) {
					for (int j = 0;j < n;j++) {
						if ((rem & (1<<j)) && ab[i][j] <= tot) {
							dp[tot][i][bit] = (dp[tot][i][bit] + dp[tot - ab[i][j]][j][rem]) % mod;
						}
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0;i <= l;i++) {
		for (int j = 0;j < n;j++) ans = (ans + dp[i][j][(1<<n) - 1]) % mod;
	}
	cout << ans << endl;
}

/*
4 10
3 6 2 9

8 35
3 7 1 5 10 2 11 6
 */

• Subtask 1: 0 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80