Submission #1226897

#TimeUsernameProblemLanguageResultExecution timeMemory
1226897TobSkyscraper (JOI16_skyscraper)C++20
100 / 100
208 ms83120 KiB
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 101, K = 1001, mod = 1e9 + 7;

inline int add(int x, int y) {return x+y<mod ? x+y : x+y-mod;}
inline int mul(int x, int y) {return (ll)x*y%mod;}

int n, l;
int a[N];
int dp[N][N][K][3];

int main () {
	FIO;
	cin >> n >> l;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	dp[0][1][0][0] = 1;
	dp[0][1][0][1+(n==1)] = 2-(n==1);
	for (int i = 1; i < n; i++) {
		int x = a[i]-a[i-1], co;
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k <= l; k++) {
				for (int g = 0; g < 3; g++) {
					co = (2*j-2-g)*x;
					if (k >= co && j > 1) {
						dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j-1][k-co][g], j-g));
						if (g && k >= co+x) dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j-1][k-co-x][g-1], 3-g));
					}
					co = (2*j-g)*x;
					if (k >= co) {
						dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j][k-co][g], 2*j-g));
						if (g && k >= co+x) dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j][k-co-x][g-1], 3-g));
					}
					co = (2*j+2-g)*x;
					if (k >= co && j < n) {
						dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j+1][k-co][g], j));
					}
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= l; i++) res = add(res, dp[n-1][1][i][2]);
	cout << res;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...