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