Submission #343719

#	Time	Username	Problem	Language	Result	Execution time	Memory
343719		Millad	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	739 ms	483680 KiB

skyscraper

// In the name of god
#include <bits/stdc++.h>
 
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;
 
const ll maxn = 1e5 + 6, MsK = 2e4, inf = 1e18, mod = 1e9 + 7;
ll n, L, a[maxn], dp[MsK][15][105], pw2[30], b[maxn];
map<pll, ll> mp;
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	pw2[0] = 1;
	for(ll i = 1; i < 16; i ++)pw2[i] = pw2[i - 1] * 2ll;
	cin >> n >> L;
	if(n == 1)return cout << 1 << endl, 0;
	for(ll i = 0; i < n; i ++)cin >> a[i];
	if(n < 9){
		for(ll i = 0; i < n; i ++)b[i] = i;
		ll ans = 0;
		while(true){
			ll dif = 0;
			for(ll i = 1; i < n; i ++)dif += abs(a[b[i]] - a[b[i - 1]]);
			if(dif <= L)ans ++;
			if(next_permutation(b, b + n))ans = ans; 
			else break;
		}
		return cout << ans << "\n", 0;
	}
	ll z = 1;
	for(ll i = 0; i < n; i ++)z *= 2;
	for(ll msk = 1; msk < z; msk ++){
		if(__builtin_popcount(msk) == 1)continue;
		if(__builtin_popcount(msk) == 2){
			vector <ll> V;
			for(ll i = 0; i < n; i ++){
				if(pw2[i] & msk)V.pb(i);
			}
			ll dif = abs(a[V[0]] - a[V[1]]);
			if(dif > L)continue;
			dp[msk][V[0]][dif] = 1;
			dp[msk][V[1]][dif] = 1;
			continue;
		}
		for(ll i = 0; i < n; i ++){
			if((pw2[i] & msk) == 0)continue;
			for(ll j = 0; j < n; j ++){
				if((pw2[j] & msk) == 0)continue;
				if(i == j)continue;
				for(ll l = 0; l <= L; l ++){
					if((l + abs(a[i] - a[j])) > L)continue;
					(dp[msk][i][l + abs(a[i] - a[j])] += dp[(msk ^ pw2[i])][j][l]) %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for(ll i = 0; i < n; i ++){
		for(ll l = 0; l <= L; l ++)(ans += dp[z - 1][i][l]) %= mod;
	}
	cout << ans << endl;
}

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