結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
![]() |
提出日時 | 2023-07-01 14:22:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,141 bytes |
コンパイル時間 | 2,038 ms |
コンパイル使用メモリ | 200,896 KB |
最終ジャッジ日時 | 2025-02-15 05:18:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main() {int n, a, b; cin >> n >> a >> b;vector<int> x(n), y(n), s(n);for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> s[i];vector dp(vector(1<<n, vector(n+1, vector<int>(n+1))));dp[0][n][n] = 1;int ans = 0;for(int st = 0; st < (1<<n); st++) {for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) {if(!dp[st][i][j]) continue;for(int k = 0; k < n; k++) {if(st >> k & 1) continue;bool strike = false;if(j == n) strike |= true;else if(i == n) {strike |= a <= abs(x[k]-x[j]) + abs(y[k]-y[j]);} else {strike |= a <= abs(x[k]-x[j]) + abs(y[k]-y[j]) + abs(x[k]-x[i]) + abs(y[k]-y[i]);}if(j < n) strike |= b <= abs(s[k]-s[j]);if(strike) {dp[st|(1<<k)][j][k] = 1;ans = max(ans, __builtin_popcount(st|(1<<k)));}}}}cout << ans << endl;}