Submission #1204089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204089		decryptifyoucan	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;

int arr[102];
int dp[102][102][102][3];

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, L;
	cin >> n >> L;

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

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	sort(arr + 1, arr + n + 1);
	arr[n + 1] = 1e4;

	dp[0][0][0][0] = 1;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			for (int k = 0; k <= L; k++)
			{
				for (int t = 0; t <= 2; t++)
				{
					int cost = (2 * j - t) * (arr[i + 1] - arr[i]);
					if (cost > k || i + j + t - 1 > n)
						continue;

					dp[i][j][k][t] += dp[i - 1][j - 1][k - cost][t];

					if (t)
						dp[i][j][k][t] += (3 - t) * dp[i - 1][j - 1][k - cost][t - 1];

					dp[i][j][k][t] += (2 * j - t) * dp[i - 1][j][k - cost][t];

					if (t == 1)
						dp[i][j][k][t] += 2 * j * dp[i - 1][j][k - cost][t - 1];

					if (t == 2)
					{
						if (j == 1)
							dp[i][j][k][t] += dp[i - 1][j][k - cost][t - 1];
						else
							dp[i][j][k][t] += (j - 1) * dp[i - 1][j][k - cost][t - 1];
					}

					if (t == 2)
					{
						if (i == n)
							dp[i][j][k][t] += dp[i - 1][j + 1][k - cost][t];
						else
							dp[i][j][k][t] += j * (j - 1) * dp[i - 1][j + 1][k - cost][t];
					}
					else if (t == 1)
					{
						dp[i][j][k][t] += j * j * dp[i - 1][j + 1][k - cost][t];
					}
					else
					{
						dp[i][j][k][t] += j * (j + 1) * dp[i - 1][j + 1][k - cost][t];
					}

					dp[i][j][k][t] %= MOD;
				}
			}
		}
	}

	int res = 0;
	for (int i = 0; i <= L; i++)
		res += dp[n][1][i][2];

	cout << res % MOD << '\n';
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43