Submission #1183400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183400		NoMercy	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	78 ms	24136 KiB

skyscraper

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

typedef long long ll;

const int MAXN = 102, MAXL = 1002, mod = 1e9 + 7;
ll dp[MAXN][MAXN][MAXL][3];

int32_t main () {

	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 

	int N, L;
	cin >> N >> L;
	vector<ll> arr(N + 1);
	for (int i = 0;i < N;i ++) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end() - 1);
	arr[N] = arr[N - 1];
	if (N == 1) {
		cout << "1\n";
		return 0;
	}

	dp[0][0][0][0] = 1;
	for (int i = 0;i < N;i ++) {
		ll diff = arr[i + 1] - arr[i];
		for (int j = 0;j <= i;j ++) {
			for (int s = 0;s <= L;s ++) {
				for (int k = 0;k < 3;k ++) if (dp[i][j][s][k] > 0) {
					int sum = s + (2 * j + 2 - k) * diff;
					if (sum <= L) {
						dp[i + 1][j + 1][sum][k] = (1LL * (j + 1 - k) * dp[i][j][s][k] + dp[i + 1][j + 1][sum][k]) % mod;
					}
					if (k < 2) {
						sum = s + (2 * j + 1 - k) * diff;
						if (sum <= L) dp[i + 1][j + 1][sum][k + 1] = (1ll * (2 - k) * dp[i][j][s][k] + dp[i + 1][j + 1][sum][k + 1]) % mod;
					}

					if (j > 0) {
						sum = s + (2 * j - k) * diff;
						if (sum <= L) {
							dp[i + 1][j][sum][k] = (1ll * (2 * j - k) * dp[i][j][s][k] + dp[i + 1][j][sum][k]) % mod;
						}
						if (k < 2) {
						    sum = s + (2 * j - k - 1) * diff;
						    if (sum <= L) {
						   		dp[i + 1][j][sum][k + 1] = (1ll * (2 - k) * dp[i][j][s][k] + dp[i + 1][j][sum][k + 1]) % mod;
						    }
						}
					}

					if (j >= 2) {
						sum = s + (2 * j - 2 - k) * diff;
						if (sum <= L) {
							dp[i + 1][j - 1][sum][k] = (1ll * (j - 1) * dp[i][j][s][k] + dp[i + 1][j - 1][sum][k]) % mod;
						}
					}
				}
			}
		}
	}

	ll ans = 0;
	for (int l = 0;l <= L;l ++) {
		ans += dp[N][1][l][2];
		ans %= mod;
	}
	cout << ans << "\n";
}

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