Submission #1261858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261858		arashmemar	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	93 ms	39496 KiB

skyscraper

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

const int maxn = 101, maxl = 2000, mod = 1e9 + 7;

int dp[maxn][maxn][3][3][maxl], a[maxn];

int main()
{
	int n, l;
	cin >> n >> l;

	if (n == 1)
	{
		cout << 1;
		return 0;
	}

	for (int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	
	long long int ans = 0;

/*	do
	{
		int ret = 0;
		for (int i = 1;i < n;i++)
		{
			ret += abs(a[i] - a[i + 1]);
		}
		if (ret <= l)
		{
			ans++;
		}
	}while (next_permutation(a + 1, a + n + 1));

	cout << ans << endl;
	ans = 0;
*/
	dp[0][0][0][0][0] = 1;
	for (int i = 0;i <= n;i++)
	{
		for (int j = 0;j <= n;j++)
		{
			for (int noe = 0;noe < 2;noe++)
			{
				for (int nos = 0;nos < 2;nos++)
				{
					for (int c = 0;c <= l;c++)
					{
						long long int p = dp[i][j][nos][noe][c];
						int cc = c + (2 * j - nos - noe) * (a[i + 1] - a[i]);
						if (p == 0 or cc > l or i == n)
						{
							continue;
						}
						dp[i + 1][j][nos][noe][cc] += p * (j - noe) % mod;
						dp[i + 1][j][nos][noe][cc] %= mod;
						dp[i + 1][j][nos][noe][cc] += p * (j - nos) % mod;
						dp[i + 1][j][nos][noe][cc] %= mod;

						dp[i + 1][j + 1][nos][noe][cc] += p;
						dp[i + 1][j + 1][nos][noe][cc] %= mod;

						if (j > 1)
						{
							dp[i + 1][j - 1][nos][noe][cc] += p * ((j - noe - nos) * (j - nos - 1) + nos * (j - nos - noe)) % mod;
							if (i == n - 1)
							{
								dp[i + 1][j - 1][nos][noe][cc] += p * nos * noe;
							}
							dp[i + 1][j - 1][nos][noe][cc] %= mod;
						}

						if (nos == 0)
						{
							dp[i + 1][j + 1][nos + 1][noe][cc] += p;
							dp[i + 1][j + 1][nos + 1][noe][cc] %= mod;

							dp[i + 1][j][nos + 1][noe][cc] += p * (j - noe) % mod;
							if (i == n - 1)
							{
								dp[i + 1][j][nos + 1][noe][cc] += p * noe;
							}
							dp[i + 1][j][nos + 1][noe][cc] %= mod;
						}
						if (noe == 0)
						{
							dp[i + 1][j][nos][noe + 1][cc] += p * (j - nos) % mod;
							if (i == n - 1)
							{
								dp[i + 1][j][nos][noe + 1][cc] += p * nos;
							}
							dp[i + 1][j][nos][noe + 1][cc] %= mod;

							dp[i + 1][j + 1][nos][noe + 1][cc] += p;
							dp[i + 1][j + 1][nos][noe + 1][cc] %= mod;
						}
					}
				}
			}
		}
	}

	for (int i = 0;i <= l;i++)
	{
		ans += dp[n][1][1][1][i];
		ans %= mod;
	}
	cout << ans;
}

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