Submission #1253295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253295		pasta	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	412 ms	123420 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

// #pragma GCC optimize("Ofast,unroll-loops,inline")   
// #pragma GCC target("avx2,bmi2,lzcnt")  

#define pb		push_back
#define all(x)	x.begin(), x.end()
// #define int ll
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn = 20;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;
const int LOG = 21;

int n, L, a[maxn], b[maxn], dp[(1 << 16)][16][120];

int main() {
	fast_io;
	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;
	}
	

	for (int msk = 0; msk < (1 << n); msk++) {
		if (__builtin_popcount(msk) == 1)
			continue;

		if (__builtin_popcount(msk) == 2) {
			vector <ll> per;
			for(ll i = 0; i < n; i ++){
				if ((1 << i) & msk)
					per.pb(i);
			}
			ll d = abs(a[per[0]] - a[per[1]]);
			if(d > L)
				continue;
			dp[msk][per[0]][d] = 1;
			dp[msk][per[1]][d] = 1;
			continue;
		}

		for (int i = 0; i < n; i++) {
			if ((1 << i) & msk == 0) continue;
			for (int j = 0; j < n; j++) {
				if ((1 << j) & msk ==0) continue;
				if (j == i) continue;

				for (int 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 ^ (1 << i)][j][l];
					dp[msk][i][l + abs(a[i] - a[j])] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		for (int cost = 0; cost <= L; cost++) {
			ans += dp[(1 << n) - 1][i][cost];
			ans %= mod;
		}
	}
	cout << ans << '\n';
}

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