結果
問題 |
No.2375 watasou and hibit's baseball
|
ユーザー |
![]() |
提出日時 | 2023-07-20 19:25:17 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,953 bytes |
コンパイル時間 | 1,169 ms |
コンパイル使用メモリ | 142,324 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-09-20 15:23:59 |
合計ジャッジ時間 | 2,821 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int main() { int N, A, B; cin >> N >> A >> B; int X[N]; int Y[N]; int K[N]; for (int i = 0; i < N; ++i) { cin >> X[i] >> Y[i] >> K[i]; } int ans = 1; int L = (1 << N); bool dp[L][N][N]; memset(dp, false, sizeof(dp)); for (int mask = 0; mask < L; ++mask) { if (__builtin_popcount(mask) != 2) continue; for (int i = 0; i < N; ++i) { if ((mask >> i & 1) == 0) continue; for (int j = 0; j < N; ++j) { if (i == j) continue; if ((mask >> j & 1) == 0) continue; int s_dist = abs(X[i] - X[j]) + abs(Y[i] - Y[j]); int k_dist = abs(K[i] - K[j]); bool cond1 = A <= s_dist; bool cond2 = B <= k_dist; if (cond1 || cond2) { dp[mask][i][j] = true; ans = 2; } } } } for (int t = 2; t < N; ++t) { for (int mask = 0; mask < L; ++mask) { if (__builtin_popcount(mask) != t) continue; for (int i = 0; i < N; ++i) { if ((mask >> i & 1) == 0) continue; for (int j = 0; j < N; ++j) { if ((mask >> j & 1) == 0) continue; if (not dp[mask][i][j]) continue; for (int k = 0; k < N; ++k) { if (mask >> k & 1) continue; int nmask = mask | (1 << k); int s_dist = abs(X[j] - X[k]) + abs(Y[j] - Y[k]); int s_dist2 = abs(X[i] - X[k]) + abs(Y[i] - Y[k]); int k_dist = abs(K[j] - K[k]); bool cond1 = B <= k_dist; bool cond2 = A <= s_dist + s_dist2; if (cond1 || cond2) { dp[nmask][j][k] = true; ans = t + 1; } } } } } } cout << ans << endl; return 0; }