oj.uz

Submission #989966

# Submission time Handle Problem Language Result Execution time Memory
989966 2024-05-29T09:03:44 Z duckindog Skyscraper (JOI16_skyscraper) C++17
20 / 100
 305 ms 106068 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];

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 26704 KB Output is correct
2 Correct 305 ms 106064 KB Output is correct
3 Correct 185 ms 106020 KB Output is correct
4 Correct 294 ms 106052 KB Output is correct
5 Correct 293 ms 105960 KB Output is correct
6 Correct 295 ms 106064 KB Output is correct
7 Correct 152 ms 106064 KB Output is correct
8 Correct 197 ms 106068 KB Output is correct
9 Correct 249 ms 105980 KB Output is correct
10 Correct 268 ms 106064 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 42 ms 26704 KB Output is correct
12 Correct 305 ms 106064 KB Output is correct
13 Correct 185 ms 106020 KB Output is correct
14 Correct 294 ms 106052 KB Output is correct
15 Correct 293 ms 105960 KB Output is correct
16 Correct 295 ms 106064 KB Output is correct
17 Correct 152 ms 106064 KB Output is correct
18 Correct 197 ms 106068 KB Output is correct
19 Correct 249 ms 105980 KB Output is correct
20 Correct 268 ms 106064 KB Output is correct
21 Runtime error 11 ms 25436 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -