結果
問題 | No.2375 watasou and hibit's baseball |
ユーザー |
![]() |
提出日時 | 2023-07-11 11:21:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 1,303 bytes |
コンパイル時間 | 407 ms |
コンパイル使用メモリ | 43,460 KB |
実行使用メモリ | 15,580 KB |
最終ジャッジ日時 | 2024-09-13 02:17:25 |
合計ジャッジ時間 | 2,285 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
/* -*- coding: utf-8 -*-** 2375.cc: No.2375 watasou and hibit's baseball - yukicoder*/#include<cstdio>#include<algorithm>using namespace std;/* constant */const int MAX_N = 14;const int NBITS = 1 << MAX_N;/* typedef *//* global variables */int xs[MAX_N], ys[MAX_N], ks[MAX_N];int dp[NBITS][MAX_N][MAX_N];/* subroutines */inline int mdist(int i, int j) {return abs(xs[j] - xs[i]) + abs(ys[j] - ys[i]);}inline void setmax(int &a, int b) { if (a < b) a = b; }/* main */int main() {int n, a, b;scanf("%d%d%d", &n, &a, &b);for (int i = 0; i < n; i++) scanf("%d%d%d", xs + i, ys + i, ks + i);for (int i = 0, bi = 1; i < n; i++, bi <<= 1)for (int j = 0, bj = 1; j < n; j++, bj <<= 1)if (i != j && (mdist(j, i) >= a || abs(ks[j] - ks[i]) >= b))dp[bi | bj][i][j] = 2;int nbits = 1 << n, maxd = 1;for (int bits = 0; bits < nbits; bits++)for (int i = 0, bi = 1; i < n; i++, bi <<= 1)for (int j = 0, bj = 1; j < n; j++, bj <<= 1)if (dp[bits][i][j] > 0) {setmax(maxd, dp[bits][i][j]);for (int k = 0, bk = 1; k < n; k++, bk <<= 1)if (! (bits & bk) &&(mdist(k, j) + mdist(k, i) >= a || abs(ks[k] - ks[j]) >= b))setmax(dp[bits | bk][j][k], dp[bits][i][j] + 1);}printf("%d\n", maxd);return 0;}