Submission #446754

#	Time	Username	Problem	Language	Result	Execution time	Memory
446754		arminatarod	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	107 ms	50968 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 105;

constexpr int MAXL = 1005;

constexpr int MAXINT = 1073741823;

constexpr int MOD = 1000000007;

int a[MAXN];

long long int dp[MAXN][MAXN][MAXL][3];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long int n, l, new_sum, answer = 0;
	cin >> n >> l;
	if (n == 1) {
		cout << 1;
		return 0;
	}
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	a[n + 1] = MAXINT;
	dp[0][0][0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int components = 1; components <= i; components++)
			for (int sum = 0; sum <= l; sum++)
				for (int endpoints = 0; endpoints <= 2; endpoints++) {
					new_sum = (2 * components - endpoints) * (a[i + 1] - a[i]);
					if (new_sum > sum || i + components + 1 - endpoints > n)
						continue;
					new_sum = sum - new_sum;
					dp[i][components][sum][endpoints] += dp[i - 1][components - 1][new_sum][endpoints];
					if (endpoints > 0)
						dp[i][components][sum][endpoints] += (3 - endpoints) * dp[i - 1][components - 1][new_sum][endpoints - 1];
					dp[i][components][sum][endpoints] += (2 * components - endpoints) * dp[i - 1][components][new_sum][endpoints];
					if (endpoints == 1)
						dp[i][components][sum][endpoints] += 2 * components * dp[i - 1][components][new_sum][0];
					else if (endpoints == 2 && i == n)
						dp[i][components][sum][endpoints] += dp[i - 1][components][new_sum][1];
					else if (endpoints == 2 && components > 1)
						dp[i][components][sum][endpoints] += (components - 1) * dp[i - 1][components][new_sum][1];
					if (endpoints == 2 && i == n)
						dp[i][components][sum][endpoints] += dp[i - 1][components + 1][new_sum][2];
					else if (endpoints == 2)
						dp[i][components][sum][endpoints] += components * (components - 1) * dp[i - 1][components + 1][new_sum][2];
					else if (endpoints == 1)
						dp[i][components][sum][endpoints] += components * components * dp[i - 1][components + 1][new_sum][1];
					else
						dp[i][components][sum][endpoints] += components * (components + 1) * dp[i - 1][components + 1][new_sum][0];
					dp[i][components][sum][endpoints] %= MOD;
				}
	for (int i = 0; i <= l; i++)
		answer = (answer + dp[n][1][i][2]) % MOD;
	cout << answer;
	return 0;
}

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