oj.uz

Submission #989965

# Submission time Handle Problem Language Result Execution time Memory
989965 2024-05-29T09:02:21 Z duckindog Skyscraper (JOI16_skyscraper) C++17
15 / 100
 298 ms 106320 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 10 ms 2648 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 26708 KB Output is correct
2 Correct 289 ms 106320 KB Output is correct
3 Correct 194 ms 106064 KB Output is correct
4 Correct 295 ms 106028 KB Output is correct
5 Correct 273 ms 106176 KB Output is correct
6 Correct 298 ms 106044 KB Output is correct
7 Correct 153 ms 106064 KB Output is correct
8 Correct 176 ms 106064 KB Output is correct
9 Correct 253 ms 106068 KB Output is correct
10 Correct 261 ms 106064 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 10 ms 2648 KB Output isn't correct
6 Halted 0 ms 0 KB -