結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2024-03-19 21:15:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 1,956 bytes |
コンパイル時間 | 3,535 ms |
コンパイル使用メモリ | 321,936 KB |
実行使用メモリ | 19,720 KB |
最終ジャッジ日時 | 2024-09-30 05:41:45 |
合計ジャッジ時間 | 5,131 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/extc++.h>int main() {using namespace std;unsigned N, A, B;cin >> N >> A >> B;vector<unsigned> X(N + 1), Y(N + 1), K(N + 1);for (unsigned i{1}; i <= N; ++i) {int x, y;cin >> x >> y >> K[i];X[i] = x + 1000;Y[i] = y + 1000;}vector<vector<unsigned>> edges(256);for (unsigned i{1}; i <= N; ++i)edges[0].emplace_back(i); // (-, -) -> (i, -)for (unsigned i{1}; i <= N; ++i)for (unsigned j{1}; j <= N; ++j)if (i != j)if (B + min(K[i], K[j]) <= max(K[i], K[j]) || A + min(X[i], X[j]) + min(Y[i], Y[j]) <= max(X[i], X[j]) + max(Y[i], Y[j]))edges[i * 16].emplace_back(j); // (i, -) -> (j, i)for (unsigned i{1}; i <= N; ++i)for (unsigned j{1}; j <= N; ++j)if (i != j)for (unsigned k{1}; k <= N; ++k)if (i != k && j != k)if (B + min(K[j], K[k]) <= max(K[j], K[k]) || A + min(X[i], X[k]) + min(Y[i], Y[k]) + min(X[j], X[k]) + min(Y[j], Y[k]) <= max(X[i], X[k]) + max(Y[i], Y[k]) + max(X[j], X[k]) + max(Y[j], Y[k]))edges[j * 16 + i].emplace_back(k); // (j, i) -> (k, j)vector<unsigned> dp(256U << N);const auto access{[&dp](unsigned visited, unsigned p_1, unsigned p_2) -> unsigned & {return dp[visited * 256 + p_1 * 16 + p_2];}};access(0, 0, 0) = 1;unsigned ans{};for (unsigned i{}; i < 1U << N; ++i)for (unsigned j{}; j <= N; ++j)for (unsigned k{}; k <= N; ++k)if (access(i, j, k)) {for (const auto nexts : edges[j * 16 + k])if (!(1 & (i >> (nexts - 1))))access(i | ((1 << nexts) / 2), nexts, j) = 1;ans = max<unsigned>(ans, popcount(i));}cout << ans << endl;return 0;}