結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2023-07-07 22:12:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,918 bytes |
コンパイル時間 | 2,106 ms |
コンパイル使用メモリ | 181,672 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-07-21 18:16:44 |
合計ジャッジ時間 | 4,260 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(false);cin.tie(0);int n, A, B;cin >> n >> A >> B;vector<tuple<int,int,int>> a(n);for(int i = 0; i < n; i++){int x, y, k;cin >> x >> y >> k;a[i] = make_tuple(x, y, k);}vector<vector<vector<bool>>> dp(1 << n, vector<vector<bool>>(n, vector<bool>(n)));for(int i = 0; i < n; i++) dp[1 << i][i][0] = true;auto f = [&](int i, int j, int k){int x1, y1, k1;int x2, y2, k2;int x3, y3, k3;tie(x1, y1, k1) = a[i];tie(x2, y2, k2) = a[j];tie(x3, y3, k3) = a[k];if(abs(k1 - k2) >= B) return true;if(abs(x1 - x2) + abs(y1 - y2) + abs(x1 - x3) + abs(y1 - y3) >= A) return true;return false;};int ans = 1;for(int i = 1; i < (1 << n); i++){int b = __builtin_popcount(i);if(b == 1){for(int j = 0; j < n; j++){if(!dp[i][j][0]) continue;int x1, y1, k1;tie(x1, y1, k1) = a[j];for(int k = 0; k < n; k++){int x2, y2, k2;tie(x2, y2, k2) = a[k];if(i == j) continue;if((A <= abs(x1 - x2) + abs(y1 - y2)) || (B <= abs(k1 - k2))) dp[i | (1 << k)][k][j] = true;}}}else{for(int j = 0; j < n; j++){if(~i >> j & 1) continue;for(int k = 0; k < n; k++){if(!dp[i][j][k]) continue;ans = max(ans, b);for(int l = 0; l < n; l++){if(i >> l & 1) continue;if(f(l, j, k)) dp[i | (1 << l)][l][j] = true;}}}}}cout << ans << '\n';}