Submission #1258918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258918		g4yuhg	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	586 ms	194732 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 400005
#define endl '\n'
using namespace std;

bool ghuy4g;

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 f[15][(1 << 14)][101], n, L, a[101];

ll dp(ll i, ll mask, ll j) {
	if (__builtin_popcount(mask) == n) {
		return 1;
	}
	if (f[i][mask][j] != -1) return f[i][mask][j];
	ll res = 0;
	if (__builtin_popcount(mask) == 0) {
		for (int u = 1; u <= n; u ++) {
			add(res, dp(u, onbit(mask, u - 1), j));
		}
		f[i][mask][j] = res;
		return res;
	}
	for (int u = 1; u <= n; u ++) {
		if (getbit(mask, u - 1)) continue;
		if (j - abs(a[u] - a[i]) >= 0) {
			add(res, dp(u, onbit(mask, u - 1), j - abs(a[u] - a[i])));
		}
	}
	f[i][mask][j] = res;
	return res;
}

bool klinh;

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

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