結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
![]() |
提出日時 | 2024-03-19 22:28:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 3,502 bytes |
コンパイル時間 | 1,236 ms |
コンパイル使用メモリ | 124,492 KB |
実行使用メモリ | 20,992 KB |
最終ジャッジ日時 | 2024-09-30 05:49:32 |
合計ジャッジ時間 | 3,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <algorithm>#include <iostream>#include <numeric>#include <string>#include <tuple>#include <utility>#include <vector>#include <limits>#define rep(i, a, b) for (int i = int(a); i < int(b); i++)using namespace std;using ll = long long int; // NOLINTusing P = pair<ll, ll>;// clang-format off#ifdef _DEBUG_#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; debug_print(__VA_ARGS__); } while(false)template<typename T, typename... Ts> void debug_print(const T &t, const Ts &...ts) { cerr << t; ((cerr << ", " << ts), ...); cerr << endl; }#else#define dump(...) do{ } while(false)#endiftemplate<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }template<typename T> bool chmin(T &a, const T& b) { if (a > b) {a = b; return true; } return false; }template<typename T> bool chmax(T &a, const T& b) { if (a < b) {a = b; return true; } return false; }template<typename T, typename... Ts> void print(const T& t, const Ts&... ts) { cout << t; ((cout << ' ' << ts), ...); cout << '\n'; }template<typename... Ts> void input(Ts&... ts) { (cin >> ... >> ts); }template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }struct Inf { template<typename T> constexpr operator T() { return numeric_limits<T>::max() / 2; } };// clang-format on#include <cmath>int popcount(ll bits) {bits = (bits & 0x5555555555555555LL) + (bits >> 1 & 0x5555555555555555LL);bits = (bits & 0x3333333333333333LL) + (bits >> 2 & 0x3333333333333333LL);bits = (bits & 0x0f0f0f0f0f0f0f0fLL) + (bits >> 4 & 0x0f0f0f0f0f0f0f0fLL);bits = (bits & 0x00ff00ff00ff00ffLL) + (bits >> 8 & 0x00ff00ff00ff00ffLL);bits = (bits & 0x0000ffff0000ffffLL) + (bits >> 16 & 0x0000ffff0000ffffLL);return (bits & 0x00000000ffffffffLL) + (bits >> 32 & 0x00000000ffffffffLL);}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int n, a, b;cin >> n >> a >> b;vector<int> x(n), y(n), k(n);rep(i,0,n){cin >> x[i] >> y[i] >> k[i];}auto dist = [&](int i, int j) -> int {return abs(x[i] - x[j]) + abs(y[i] - y[j]);};const int bits = 1 << n;auto dp = make_v(bits, n + 1, n + 1, false);rep(i,0,n){dp[1 << i][n][i] = true;}rep(bit, 1, bits) {rep(i,0,n+1) {rep(j,0,n+1){if (!dp[bit][i][j]) continue;rep(t,0,n) {if ((bit >> t) & 1) continue;int dist1 = dist(j, t);int pop = popcount(bit);bool ok = false;if (pop == 1 && a <= dist1) ok = true;int diff = abs(k[t] - k[j]);if (b <= diff) ok = true;if (i != n) {int dist2 = dist(t, j) + dist(t, i);if (a <= dist2) {ok = true;}}if (ok) {dp[bit | 1 << t][j][t] = true;}}}}}int ans = 0;rep(bit,0,bits) {rep(i,0,n+1){rep(j,0,n+1) {if (dp[bit][i][j]) {chmax(ans, popcount(bit));}}}}print(ans);return 0;}