Submission #989966

#	Time	Username	Problem	Language	Result	Execution time	Memory
989966		duckindog	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	305 ms	106068 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int N = 100 + 10,
					L = 1000 + 10,
					M = 1'000'000'007;
int n, l;
int a[N];

int f[1 << 14][14 + 1][N];

namespace sub1 { 
	void solve() { 
		vector<int> per(n); iota(per.begin(), per.end(), 1);
		int answer = 0;
		do { 
			int sum = 0;
			for (int i = 1; i < n; ++i) sum += abs(a[per[i]] - a[per[i - 1]]);
			answer += sum <= l;
		} while (next_permutation(per.begin(), per.end()));

		cout << answer << "\n";
	}
}

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> l;
	for (int i = 1; i <= n; ++i) cin >> a[i];

	if (n <= 8) { sub1::solve(); return 0; }

	auto add = [&](auto& x, const auto& y) { 
		x += y;
		if (x >= M) x -= M;
	};

	for (int i = 1; i <= n; ++i) f[1 << i - 1][i][0] = 1;
	
	for (int bit = 1; bit < (1 << n); ++bit) { 
		if (__builtin_popcount(bit) == 1) continue;
		for (int i = 1; i <= n; ++i) { 
			if (!(bit >> i - 1 & 1)) continue;
			for (int j = 0; j <= l; ++j) { 
				auto& ret = f[bit][i][j];
				for (int t = 1; t <= n; ++t) { 
					if (!(bit >> t - 1 & 1) || i == t || abs(a[i] - a[t]) > j) continue;
					add(ret, f[bit & ~(1 << i - 1)][t][j - abs(a[i] - a[t])]);
				}
			}
		}
	}
	
	int answer = 0;
	for (int i = 1; i <= n; ++i) { 
		for (int j = 0; j <= l; ++j) add(answer, f[(1 << n) - 1][i][j]);
	}
	cout << answer << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:40:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |  for (int i = 1; i <= n; ++i) f[1 << i - 1][i][0] = 1;
      |                                      ~~^~~
skyscraper.cpp:45:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   45 |    if (!(bit >> i - 1 & 1)) continue;
      |                 ~~^~~
skyscraper.cpp:49:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   49 |      if (!(bit >> t - 1 & 1) || i == t || abs(a[i] - a[t]) > j) continue;
      |                   ~~^~~
skyscraper.cpp:50:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |      add(ret, f[bit & ~(1 << i - 1)][t][j - abs(a[i] - a[t])]);
      |                              ~~^~~

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