結果
問題 |
No.2375 watasou and hibit's baseball
|
ユーザー |
|
提出日時 | 2023-07-12 00:04:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 1,646 bytes |
コンパイル時間 | 1,307 ms |
コンパイル使用メモリ | 135,656 KB |
最終ジャッジ日時 | 2025-02-15 09:52:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <functional> #include <cmath> #include <iomanip> #include <stack> #include <queue> #include <numeric> #include <map> #include <unordered_map> #include <set> #include <fstream> #include <chrono> #include <random> #include <bitset> //#include <atcoder/all> #define rep(i,n) for(int i=0;i<(n);i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) ((int)(x).size()) #define pb push_back using ll = long long; using namespace std; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;} ll lcm(ll a, ll b) {return a/gcd(a,b)*b;} int main(){ 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]; vector dp(1<<N,vector(N,vector<ll>(N,0))); rep(i,N){ dp[1<<i][0][i] = 1; } rep(i,1<<N){ rep(j,N){ rep(k,N){ if(dp[i][j][k]==0) continue; int p = __builtin_popcount(i); rep(l,N){ if(i&(1<<l)) continue; if(A<=abs(X[k]-X[l])+abs(Y[k]-Y[l])) dp[i+(1<<l)][k][l] = 1; if(B<=abs(K[k]-K[l])) dp[i+(1<<l)][k][l] = 1; if(p>=2){ if(A<=abs(X[k]-X[l])+abs(Y[k]-Y[l])+abs(X[j]-X[l])+abs(Y[j]-Y[l])) dp[i+(1<<l)][k][l] = 1; } } } } } int ans = 0; rep(i,1<<N){ rep(j,N){ rep(k,N){ if(dp[i][j][k]) chmax(ans,__builtin_popcount(i)); } } } cout << ans << endl; return 0; };