Submission #1192859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192859		qrn	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	1 ms	1296 KiB

skyscraper

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e18;
const intt mxN = 105;
const intt mxA = 1005;
const intt L = 21;

intt dp[mxN][mxN][mxA][3];

void solve() {
	intt N, L;
	cin >> N >> L;
	vector<intt> A(N+1);
	for(intt i = 1; i <= N; i++) {
		cin >> A[i];
	}
	sort(ALL(A));

	if(N == 1) {
		cout << 0 << endl;
		return;
	}

	dp[0][0][0][0] = 1;
	for(intt i = 1; i <= N; i++) {
		intt cost = 0;
		if(i != N) cost = A[i + 1] - A[i];
		for(intt j = 0; j < i; j++) {
			for(intt k = 0; k <= L; k++) {
				for(intt z = 0; z < 3; z++) {
					intt ns = (2 * (j + 1) - z) * cost;
					if(k + ns <= L) {
						dp[i][j + 1][k + ns][z] += dp[i-1][j][k][z] * (j + 1 - z);
						dp[i][j + 1][k + ns][z] %= mod;

					}
					ns -= cost;
					if(z != 2 && k + ns <= L) {
						intt ways = 0;
						if(z == 1) ways = 1;
						else ways = 2;
						dp[i][j + 1][k + ns][z + 1] += dp[i-1][j][k][z] * ways;
						dp[i][j + 1][k + ns][z + 1] %= mod;
					}
					ns = (2 * j - z) * cost;
					if(k + ns <= L && j >= 1) {
						dp[i][j][k + ns][z] += dp[i-1][j][k][z] * (2 * j - z);
						dp[i][j][k + ns][z] %= mod;
					}
					ns -= cost;
					if(z != 2 && k + ns <= L) {
						intt ways = 0;
						if(z == 1) ways = 1;
						else ways = 2;
						dp[i][j][k + ns][z + 1] += dp[i-1][j][k][z] * ways;
						dp[i][j][k + ns][z + 1] %= mod;
					}
					ns = (2 * (j - 1) - z) * cost;
					if(k + ns <= L && j >= 2) {
						dp[i][j - 1][k + ns][z] += dp[i-1][j][k][z] * (j - 1);
						dp[i][j - 1][k + ns][z] %= mod;
					}
				}
			}
		}
	}
	
	intt ans = 0;
	for(intt i = 0; i <= L; i++) {
		ans += dp[N][1][i][2];
		ans %= mod;
	}
	cout << ans << endl;
}

signed main() {

	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1, idx = 1;
	// cin >> tst;
	while(tst--) {
		// cout << "Case " << idx << ":" << endl; 
		solve();
		// idx++;
	}
}

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