Submission #26990

#	Time	Username	Problem	Language	Result	Execution time	Memory
26990		Bruteforceman	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	99 ms	132024 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long Long;
int a[110];
int n;
const int mod = 1000000007;
int L;
int fn[105][105][3][1005];

int dp(int i, int group, int oneside, int value) {
	value += (a[i] - a[i-1]) * (2 * group + oneside);
	if(value > L) return 0;
	if(group < 0) return 0;
	if(oneside > 2) return 0;
	if(i == n) {
		if(group == 0 and oneside) return 1;
		else return 0;
	}
	if(fn[i][group][oneside][value] != -1) return fn[i][group][oneside][value];

	Long ans = 0;
	ans += 1LL * (2 * group + oneside) * dp(i + 1, group, oneside, value);
	ans += 1LL * (group + 1) * dp(i + 1, group + 1, oneside, value);
	ans += 1LL * (group + oneside - 1) * dp(i + 1, group - 1, oneside, value);
	ans += 1LL * (2 - oneside) * dp(i + 1, group, oneside + 1, value);
	ans += 1LL * (2 - oneside) * dp(i + 1, group - 1, oneside + 1, value);
	ans %= mod;
	return fn[i][group][oneside][value] = ans;
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie (nullptr);
	
	cin >> n >> L;
	if(n == 1) {
		cout << 1 << endl;
		exit(0);
	} 
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a+1, a+n+1);
	memset(fn, -1, sizeof fn);
	cout << dp(1, 0, 0, 0) << endl;
	return 0;
}

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