제출 #1043363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1043363		Aldas25	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	48 ms	129876 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;
const int MAXN = 110;
const int MAXL = 1010;

int n, l;
int a[MAXN];
ll dp[MAXN][MAXN][MAXL][3];

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

	cin >> n >> l;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1);

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

	dp[0][0][0][0] = 1;
	a[n+1] = MAXL;

	for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) for (int m = 0; m <= 2; m++) {
		int delta = (a[i+1] - a[i]) * (2 * j - m);
		
		for (int k = delta; k <= l; k++) {
			int prevK = k - delta;
			ll val = 0;
			// Case 1
			val += dp[i-1][j-1][prevK][m];
			
			// Case 2
			if (m > 0) 
				val += ((ll)(3 - m)) * dp[i-1][j-1][prevK][m-1];

			// Case 3
			val += ((ll)(2 * j - m)) * dp[i-1][j][prevK][m];
			
			// Case 4
			if (m == 1) {
				val += ((ll)(2 * j)) * dp[i-1][j][prevK][m-1];
			} else if (m == 2 && j == 1 && i == n)
				val += dp[i-1][j][prevK][m-1];
			else if (m == 2 && j != 1)
				val += ((ll)(j-1)) * dp[i-1][j][prevK][m-1];

			// Case 5
			if (i == n && j == 1 && m == 2)
				val += dp[i-1][j+1][prevK][m];
			else if (i != n) {
				ll mult = 0;
				if (m == 0) mult = (j + 1) * j;
				else if (m == 1) mult = j * j;
				else mult = (j - 1) * j;

				val += mult * dp[i-1][j+1][prevK][m];
			}

			dp[i][j][k][m] = val % MOD;
		}
	}

	ll ans = 0;
	for (int k = 0; k <= l; k++) ans = (ans + dp[n][1][k][2]) % MOD;

	cout << (ans % MOD) << "\n";

	return 0;
}

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