結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
![]() |
提出日時 | 2023-07-09 20:43:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 1,079 bytes |
コンパイル時間 | 1,828 ms |
コンパイル使用メモリ | 196,608 KB |
最終ジャッジ日時 | 2025-02-15 09:23:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(v) v.begin(), v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; int dp[1<<14][14][14]; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n,a,b; cin>>n>>a>>b; vector<int> X(n),Y(n),K(n); rep(i,n) cin>>X[i]>>Y[i]>>K[i]; auto dis=[&](int i,int j)->int{ return abs(X[i]-X[j])+abs(Y[i]-Y[j]); }; rep(i,n){ rep(j,n){ if(i==j) continue; if(a>dis(i,j) && b>abs(K[i]-K[j])) continue; dp[(1<<i)|(1<<j)][i][j]=1; } } for(int bit=0;bit<(1<<n)-1;bit++){ rep(i,n){ rep(j,n){ if(dp[bit][i][j]==0) continue; rep(k,n){ if(bit&(1<<k)) continue; if(b>abs(K[j]-K[k]) && a>dis(k,j)+dis(k,i)) continue; dp[bit|(1<<k)][j][k]=1; } } } } int ans=1; for(int bit=0;bit<(1<<n);bit++){ rep(i,n){ rep(j,n){ if(dp[bit][i][j]){ ans=max(ans,__builtin_popcount(bit)); } } } } cout<<ans<<endl; return 0; }