結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
|
提出日時 | 2023-07-07 21:28:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 1,073 bytes |
コンパイル時間 | 1,883 ms |
コンパイル使用メモリ | 194,376 KB |
最終ジャッジ日時 | 2025-02-15 06:47:41 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;using pii=pair<int,int>;#define all(a) a.begin(),a.end()#define pb push_back#define sz(a) ((int)a.size())const int N=14;int n,x[N],y[N],k[N],A,B;bool dp[1<<N][N][N];int dis(int i, int j){return abs(x[i]-x[j])+abs(y[i]-y[j]);}signed main(){ios_base::sync_with_stdio(0),cin.tie(0);cin >> n >> A >> B;for(int i=0; i<n; ++i) cin >> x[i] >> y[i] >> k[i];for(int i=0; i<n; ++i) dp[1<<i][i][i]=1;for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(i!=j&&(dis(i,j)>=A||abs(k[i]-k[j])>=B)) dp[(1<<i)+(1<<j)][i][j]=1;for(int s=0; s<(1<<n); ++s) if(__builtin_popcount(s)>=2){for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(dp[s][i][j]){for(int t=0; t<n; ++t) if(!(s>>t&1)){if(abs(k[t]-k[j])>=B||dis(t,i)+dis(t,j)>=A) dp[s^(1<<t)][j][t]=1;}}}int res=1;for(int s=0; s<(1<<n); ++s) for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(dp[s][i][j]) res=max(res,__builtin_popcount(s));cout << res << "\n";}