Submission #989965

#	Time	Username	Problem	Language	Result	Execution time	Memory
989965		duckindog	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	298 ms	106320 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];

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

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

	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:24:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |  for (int i = 1; i <= n; ++i) f[1 << i - 1][i][0] = 1;
      |                                      ~~^~~
skyscraper.cpp:29:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   29 |    if (!(bit >> i - 1 & 1)) continue;
      |                 ~~^~~
skyscraper.cpp:33:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   33 |      if (!(bit >> t - 1 & 1) || i == t || abs(a[i] - a[t]) > j) continue;
      |                   ~~^~~
skyscraper.cpp:34:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |      add(ret, f[bit & ~(1 << i - 1)][t][j - abs(a[i] - a[t])]);
      |                              ~~^~~

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