Submission #1259248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259248		g4yuhg	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	260 ms	260636 KiB

skyscraper

//Huyduocdithitp
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
#define pii pair<ll, ll> 
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 105
#define endl '\n'
using namespace std;

bool ghuy4g;

const ll inf = 1e18;

const ll mod = 1e9 + 7;

ll getbit(ll mask, ll i) {
	return (mask >> i) & 1;
}

ll onbit(ll mask, ll i) {
	return mask | (1 << i);
}

void add(ll &u, ll v) {
	u += v;
	if (u >= mod) u -= mod;
}

ll n, L, a[N];
ll f[N][N][1005][3];

ll dp(ll i, ll j, ll k, ll m) {
	if (i > n) {
		if (j == 1 && m == 2 && k <= L) return 1;
		return 0;
	}
	if (i - 1 + j + 1 - m > n) return 0;
	if (f[i][j][k][m] != -1) return f[i][j][k][m];
	ll res = 0;
	
	// case 1
	if (1) {
		ll new_j = j + 1, new_m = m;
		ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
		if (k + cost <= L) {
			add(res, dp(i + 1, j + 1, k + cost, m));
		}
	}
	// case 2
	if (2 && m + 1 <= 2) {
		ll base = 2 - m;
		ll new_j = j + 1, new_m = m + 1;
		ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
		if (k + cost <= L) {
			add(res, dp(i + 1, j + 1, k + cost, m + 1) * base % mod);
		}
	}
	// case 3
	if (3 && j - 1 >= 1) {
		ll base = 1;
		if (m == 2) {
			if (i == n) base = 1;
			else base = (j - 1) * (j - 2);
		}
		else if (m == 0) {
			base = (j - 1) * j;
		}
		else if (m == 1){
			base = (j - 1) * (j - 1);
		}
		ll new_j = j - 1, new_m = m;
		ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
		if (k + cost <= L) {
			add(res, dp(i + 1, j - 1, k + cost, m) * base % mod);
		}
	}
	// case 4
	if (4) {
		ll base = 2 * j - m;
		ll new_j = j, new_m = m;
		ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
		if (k + cost <= L) {
			add(res, dp(i + 1, j, k + cost, m) * base % mod);
		}
	}
	// case 5
	if (5 && m + 1 <= 2) {
		ll new_j = j, new_m = m + 1;
		ll base = 0;
		if (m == 0) {
			base = 2 * j;
		}
		else if (m == 1) {
			if (i == n) {
				base = 1;
			}
			else base = j - 1;
		}
		ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
		if (k + cost <= L) {
			add(res, dp(i + 1, j, k + cost, m + 1) * base % mod);
		}
	}
	f[i][j][k][m] = res;
	return res;
}

void sub2() {
	if (n == 1) {
		cout << 1;
		exit(0);
	}
	memset(f, -1, sizeof(f));
	sort(a + 1, a + 1 + n);
	cout << dp(1, 0, 0, 0) << endl;
}

bool klinh;

signed main() {
    faster;
    
    cin >> n >> L;
    a[n + 1] = inf;
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i];
    }
    
    sub2();
 	    
 	cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
 	
 	cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl;
 	    
    return 0;
}

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