Submission #1261419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261419		Bui_Quoc_Cuong	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	69 ms	25532 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
#define int long long
void add(int &x, const int y){
	x+= y;
	if (x >= MOD) x-= MOD;
}
int n, L;
int a[1006];
int dp[105][105][1005][3];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> n >> L;
	if(n == 1){
		cout << 1;
		return 0;
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	dp[0][0][0][0] = 1;
	for(int i = 0; i <= n - 1; i++) for(int j = 0; j <= n; j++) for(int s = 0; s <= L; s++){
		for(int e = 0; e <= 2; e++) if(dp[i][j][s][e] > 0){
			int g = (2 * j - e) * (a[i + 1] - a[i]);
			if (s + g > L) continue;
			/// tao 1 tplt moi va khong chua ket thuc
			add(dp[i + 1][j + 1][s + g][e], dp[i][j][s][e]);

			/// tao 1 tplt moi va ket thuc
			add(dp[i + 1][j + 1][s + g][e + 1], 1LL * dp[i][j][s][e] * (2 - e) % MOD);

			/// chen a[i] vao 1 tplt va ko ket thuc
			add(dp[i + 1][j][s + g][e], 1LL * (2 * j - e) * dp[i][j][s][e] % MOD);

			/// chen a[i] vao 1 tplt va ket thuc
			if(e == 0){
				add(dp[i + 1][j][s + g][1], 1LL * 2 * j % MOD * dp[i][j][s][e] % MOD);
			}
			if(e == 1){
				if(j == 1 && i + 1 == n){
					add(dp[i + 1][j][s + g][2], dp[i][j][s][e]);
				} else{
					add(dp[i + 1][j][s + g][2], 1LL * dp[i][j][s][e] * (j - 1) % MOD);
				}
			}

			/// dung a[i] noi 2 tplt
			if(j >= 2){
				if(e == 0){
					add(dp[i + 1][j - 1][s + g][0], 1LL * dp[i][j][s][e] * j % MOD * (j - 1) % MOD);
				}
				if(e == 1){
					add(dp[i + 1][j - 1][s + g][1], 1LL * dp[i][j][s][e] * (j - 1) % MOD * (j - 1) % MOD);
				}
			}
			if(e == 2){
				if(j == 2 && i + 1 == n){
					add(dp[i + 1][j - 1][s + g][2], dp[i][j][s][e]);
				} else if(j >= 3){
					add(dp[i + 1][j - 1][s + g][2], 1LL * dp[i][j][s][e] * (j - 2) % MOD * (j - 1) % MOD);
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= L; i++) add(ans, dp[n][1][i][2]);
	cout << ans;
	return 0;
}

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