제출 #107398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107398		fmrozaqi	Skyscraper (JOI16_skyscraper)	C++14	5 / 100	171 ms	181700 KiB

skyscraper

#include <bits/stdc++.h>
#define REP(a, b) for(int a = 0; a < b; a++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> LL;
typedef vector<int> vi;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//shuffle(permutation.begin(), permutation.end(), rng);
//uniform_int_distribution<int>(l, r)(rng);
const int MAXN = 105;

int n, L;
int A[MAXN];
int DP[MAXN][MAXN][2][2][10 * MAXN];

int rek(int pos, int nyak, int l, int r, int sum) {
	if (sum > L) return 0;
	if (pos == n) {
		if (nyak == 0) return 1;
		return 0;
	}
	int &ret = DP[pos][nyak][l][r][sum];
	if (ret != -1) return ret;
	int sek = 0;
	if (pos) sek = sum + ((l + r + 2 * nyak) * (A[pos] - A[pos - 1]));
	ret = 0;
	
	if (pos == (n - 1)) {
		ret = (ret + rek(pos + 1, nyak, 1, 1, sek)) % MOD;
		return ret;
	}
	
	ret = (ret + rek(pos + 1, nyak, 1, r, sek)) % MOD;
	ret = (ret + rek(pos + 1, nyak, l, 1, sek)) % MOD;
	if (nyak) {
		ll tmp = rek(pos + 1, nyak - 1, 1, r, sek);
		tmp = tmp * nyak % MOD;
		ret = (ret + tmp) % MOD;
		
		tmp = rek(pos + 1, nyak - 1, l, 1, sek);
		tmp = tmp * nyak % MOD;
		ret = (ret + tmp) % MOD;
		
		tmp = rek(pos + 1, nyak, l, r, sek);
		tmp = tmp * nyak % MOD;
		tmp = tmp * 2 % MOD;
		ret = (ret + tmp) % MOD;
		
		if (nyak >= 2) {
			tmp = rek(pos + 1, nyak - 1, l, r, sek);
			tmp = tmp * nyak % MOD;
			tmp = tmp * (nyak - 1) % MOD;
			ret = (ret + tmp) % MOD;
		}
	}
	ret = (ret + rek(pos + 1, nyak + 1, l, r, sek));
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	memset(DP, -1, sizeof DP);
	cin >> n >> L;
	REP(i, n) cin >> A[i];
	sort(A, A + n);
	cout << rek(0, 0, 0, 0, 0) << '\n';
}

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