結果
問題 |
No.2375 watasou and hibit's baseball
|
ユーザー |
![]() |
提出日時 | 2023-07-08 01:38:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 2,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 1,125 ms |
コンパイル使用メモリ | 108,484 KB |
実行使用メモリ | 17,960 KB |
最終ジャッジ日時 | 2024-07-21 21:51:02 |
合計ジャッジ時間 | 2,590 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<set> #include<queue> #include<cassert> using namespace std; using ll = long long; int dp[1<<14][15][15]; int main(){ int n,a,b; cin>>n>>a>>b; vector<int> x(n),y(n),k(n); for(int i = 0;i<n;i++) cin>>x[i]>>y[i]>>k[i]; for(int i = 0;i<1<<n;i++) for(int j = 0;j<n;j++) for(int l = 0;l<n;l++) dp[i][j][l] = 0; dp[0][0][0] = 1; for(int i = 1;i<1<<n;i++){ if(__builtin_popcount(i)==1){ int ni = 0; for(int j = 0;j<n;j++) if(i>>j&1) ni = j; for(int j = 0;j<n;j++) dp[i][j][ni] = 1; } for(int j = 0;j<n;j++){ for(int l = 0;l<n;l++){ if(dp[i][j][l]==0) continue; for(int m = 0;m<n;m++){ if(i>>m&1) continue; int nxt = i | 1<<m; int cnt = __builtin_popcount(nxt); assert(cnt>=2); bool ok = false; if(abs(k[l]-k[m])>=b) dp[nxt][l][m] = 1; if(cnt==2){ if(a<=abs(x[l]-x[m])+abs(y[l]-y[m])) dp[nxt][l][m] = 1; } if(cnt>=3){ if(a<=abs(x[l]-x[m])+abs(y[l]-y[m])+abs(x[j]-x[m])+abs(y[j]-y[m])) dp[nxt][l][m] = 1; } } } } } int ans = 0; for(int i = 0;i<1<<n;i++) for(int j = 0;j<n;j++) for(int l = 0;l<n;l++) if(dp[i][j][l]) ans = max(ans,__builtin_popcount(i)); cout<<ans<<endl; }