結果
問題 | 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;}