제출 #1086345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086345		Raiden	Skyscraper (JOI16_skyscraper)	C++14	0 / 100	72 ms	136496 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX = 105;
int dp[3][MAX][MAX][MAX * 10], n;
int arr[MAX];
int f(int alive_ends, int i,int components, int sm){
	if(alive_ends < 0) return 0;
	if(sm < 0) return 0;
	if(i == n) return alive_ends == 0 && components == 1;
	int &ret = dp[alive_ends][i][components][sm];
	if(~ret) return ret;
	ret = 0;
	sm -= (2 * components - alive_ends) * (arr[i] - arr[i - 1]);
	ret = (ret + 1LL * (2 * components - 2 + alive_ends) * f(alive_ends, i + 1, components, sm)) % MOD;
	if(components) ret = (ret + 1LL * alive_ends * f(alive_ends - 1, i + 1, components, sm)) % MOD;
	ret = (ret + 1LL * (components - 1 + alive_ends) * f(alive_ends, i + 1, components + 1, sm)) % MOD;
	if(alive_ends) ret = (ret + 1LL * alive_ends * f(alive_ends - 1, i + 1, components + 1, sm)) % MOD;
	if(components) ret = (ret + 1LL * (components - 1) * f(alive_ends, i + 1, components - 1, sm)) % MOD;
	return ret;
}
void solve(){
	int k;
	cin >> n >> k;
	memset(dp, -1, sizeof dp);
	for(int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);
	if(n == 1){
		cout << 1 << '\n';
		return ;
	}
	cout << (f(2, 0, 0, k)) % MOD << '\n';
 
}
 
int32_t main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t--) solve();
}

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