結果
| 問題 |
No.2375 watasou and hibit's baseball
|
| コンテスト | |
| ユーザー |
 watasou1543
|
| 提出日時 | 2023-06-21 15:59:55 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 238 ms / 2,000 ms |
| コード長 | 13,664 bytes |
| コンパイル時間 | 2,945 ms |
| コンパイル使用メモリ | 175,488 KB |
| 実行使用メモリ | 61,056 KB |
| 最終ジャッジ日時 | 2024-07-08 08:44:21 |
| 合計ジャッジ時間 | 8,877 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#pragma region watasou
/*
the pen is mightier than the sword.
-エドワード・ブルワー＝リットン-
KCLC44TH watasou1543.
*/
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//マクロ宣言
#define rep(i, a, b) for (ll i = a; i < b; i++)
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<ll>>;
using V = vector<ll>;
const ll mod=998244353;
const ll MOD=1000000007;
const ll INF=1000000000000000000;
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc="abcdefghijklmnopqrstuvwxyz";
string Y = "Yes";
string N = "No";
#define gcd __gcd
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define fix(n) fixed << setprecision(n)
#define print(n) cout << n << endl
#define si size()
#define in(n) insert(n)
//関数宣言
template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
ll jou(ll N,ll k){
ll i=0;
ll p=N;
ll Ans=0;
while(k>=(1<<i)){
if(k&(1<<i)){
Ans+=p;
}
p*=p;
i++;
}
return Ans;
}
//DFS
map<ll,vector<ll>>Gra;
map<ll,bool>visited;// false=not visited, true=visited
void DFS(int pos){
visited[pos]=true;
for(int i : Gra[pos]){
if(visited[i]==false){
DFS(i);
}
}
}
vector<pair<long long, long long> > pri(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
const vector<int>dx = {0, 1, 0, -1};
const vector<int>dy = {1, 0, -1, 0};
vector<vector<ll>> BFS(int H, int W, const vector<string> &G, pair<int, int> s) {
vector<vector<ll>> dist(H, vector<ll>(W, -1)); //すべての頂点を未訪問に初期化
queue<pair<int, int>> que;
//初期条件 (頂点sを初期頂点とする)
dist[s.first][s.second] = 0;
que.push(s); // sを探索済み頂点に
// BFS開始
while (!que.empty()) {
pair<int, int> v = que.front();
que.pop();
//頂点vからたどれる頂点を全て調べる
for (int i = 0; i < 4; i++) {
int X = dx[i] + v.first;
int Y = dy[i] + v.second;
if (X < 0 || X >= H || Y < 0 || Y >= W) continue;
//すでに発見済みの頂点は探索しない
if (dist[X][Y] != -1 || G[X][Y] == '#') continue;
//新たな未探索点xについて距離情報を更新してキューに挿入
dist[X][Y] = dist[v.first][v.second] + 1;
que.push(make_pair(X, Y));
}
}
return dist;
}
vector<bool>sosuu(long long n){
vector<bool> isprime(n+1, true);
// 0, 1 は予めふるい落としておく
isprime[0] = isprime[1] = false;
// ふるい
for (int p = 2; p <= n; ++p) {
// すでに合成数であるものはスキップする
if (!isprime[p]) continue;
// p 以外の p の倍数から素数ラベルを剥奪
for (int q = p * 2; q <= n; q += p) {
isprime[q] = false;
}
}
return isprime;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// Union-Find
struct UnionFind {
vector<int> par, rank, siz;
// 構造体の初期化
UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
// 根を求める
int root(int x) {
if (par[x]==-1) return x; // x が根の場合は x を返す
else return par[x] = root(par[x]); // 経路圧縮
}
// x と y が同じグループに属するか (= 根が一致するか)
bool same(int x, int y) {
return root(x)==root(y);
}
// x を含むグループと y を含むグループを併合する
bool unite(int x, int y) {
int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
if (rx==ry) return false; // すでに同じグループのときは何もしない
// union by rank
if (rank[rx]<rank[ry]) swap(rx, ry); // ry 側の rank が小さくなるようにする
par[ry] = rx; // ry を rx の子とする
if (rank[rx]==rank[ry]) rank[rx]++; // rx 側の rank を調整する
siz[rx] += siz[ry]; // rx 側の siz を調整する
return true;
}
// x を含む根付き木のサイズを求める
int size(int x) {
return siz[root(x)];
}
};
//ワーシャルフロイド
Graph D;
void warshall_floyd(int n) {
for (int k = 0; k < n; k++){ // 経由する頂点
for (int i = 0; i < n; i++) { // 始点
for (int j = 0; j < n; j++) { // 終点
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}
}
}
}
ll string_mod(string s, ll mod){
ll rest = 0;
for(char c : s){
ll v = c-'0';
rest = (rest*10 + v) % mod;
}
return rest;
}
ll ro(ll a,ll b,Graph &G){
ll now=a;
rep(i,0,25){
if(b&(1LL<<i)){
now=G[now][i];
}
}
return now;
}
typedef pair<ll,int>P;
struct edge{int to;ll cost;};
vector<ll> dijkstra(vector<vector<edge>> graph, int n, int start, ll INF){
priority_queue<P,vector<P>,greater<P>>que;
vector<ll>dst(n,INF);
dst[start]=0;
que.push(P(0,start));
while(que.size()){
ll d=que.top().first;
int u=que.top().second;
que.pop();
if(dst[u]<d) continue;
for(int i=0;i<(int)graph[u].size();++i){
int v=graph[u][i].to;
ll cost=graph[u][i].cost;
if(dst[v]>d+cost){
dst[v]=d+cost;
que.push(P(dst[v],v));
}
}
}
return dst;
}
// グラフ、頂点の入次数、頂点数を受け取り、そのトポロジカルソートを記録した配列を返す関数
vector<ll> topological_sort(vector<vector<ll>> &G, vector<ll> &indegree, int V) {
// トポロジカルソートを記録する配列
vector<ll> sorted_vertices;
// 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する
queue<int> que;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
// キューが空になるまで、操作1~3を繰り返す
while (que.empty() == false) {
// キューの先頭の頂点を取り出す
int v = que.front();
que.pop();
if(que.size()!=1){
print(N);
exit(0);
}
// その頂点と隣接している頂点の入次数を減らし、0になればキューに追加
for (int i = 0; i < (int)G[v].size(); i++) {
int u = G[v][i];
indegree[u] -= 1;
if (indegree[u] == 0) que.push(u);
}
// 頂点vを配列の末尾に追加する
sorted_vertices.push_back(v);
}
// トポロジカルソートを返す
return sorted_vertices;
}
template <typename T>
struct RMQ {
const T INF = numeric_limits<T>::max();
int n; // 葉の数
vector<T> dat; // 完全二分木の配列
RMQ(int n_):n(),dat(n_*4,INF) { // 葉の数は 2^x の形
int x = 1;
while (n_>x) {
x*=2;
}
n=x;
}
void update(int i,T x) {
i+=n-1;
dat[i]=x;
while(i>0){
i=(i-1)/2;//parent
dat[i]=min(dat[i*2+1],dat[i*2+2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) {
return INF;
} else if (a <= l && r <= b) {
return dat[k];
} else {
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
};
int op(int a,int b){
return (a^b);
}
int e(){
return 0;
}
//using mint =modint998244353;
#define debug cout << "OK" << endl;
#pragma region template
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p)
{
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
for (int i = 0; i < (int)v.size(); i++)
{
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
for (int i = 0; i < (int)v.size(); i++)
{
os << v[i] << endl;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v)
{
for (int i = 0; i < (int)v.size(); i++)
{
os << "i = " << i << endl;
os << v[i];
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
for (T &in : v)
is >> in;
return is;
}
// template <typename T, typename S>
// ostream &operator<<(ostream &os, const map<T, S> &mp)
// {
// for ((auto &[key, val]) : mp)
// {
// os << key << ":" << val << " ";
// }
// return os;
// }
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
auto itr = st.begin();
for (int i = 0; i < (int)st.size(); i++)
{
os << *itr << (i + 1 != (int)st.size() ? " " : "");
itr++;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
auto itr = st.begin();
for (int i = 0; i < (int)st.size(); i++)
{
os << *itr << (i + 1 != (int)st.size() ? " " : "");
itr++;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, queue<T> q)
{
while (q.size())
{
os << q.front() << " ";
q.pop();
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, deque<T> q)
{
while (q.size())
{
os << q.front() << " ";
q.pop_front();
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, stack<T> st)
{
while (st.size())
{
os << st.top() << " ";
st.pop();
}
return os;
}
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq)
{
while (pq.size())
{
os << pq.top() << " ";
pq.pop();
}
return os;
}
#pragma endregion template
//-------------- -----------------------------------------------------------
#pragma endregion watasou
/*
切り上げは(a+b-1)/bでできる
cin忘れに注意
制約を見よう ヒントが多分ある
N<=100だとO(N^3)かもしれない
N<=10だとO(2^N)かもO(!N)かもしれない
N<=9*(10^18)だとO(√N)の場合通らないことがある
わかんなくなったら問題文を読み直そう
*/
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
#include<fstream>
V x(15,0),y(15,0),k(15,0);
ll d(ll a,ll b){
return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main(){
int n,a,b;
cin >> n >> a >> b;
int c=n+1;
rep(i,1,n+1){
cin >> x[i] >> y[i] >> k[i];
}
ll dp[(1LL<<c)][n+1][n+1];
rep(i,0,(1LL<<c))rep(j,0,n+1)rep(l,0,n+1){
dp[i][j][l]=0;
}
rep(i,1,n+1){
dp[(1LL<<i)+1][0][i]=1;
}
rep(i,0,(1LL<<c)){
rep(j,0,n+1){
rep(l,1,n+1){
if(j==l)continue;
if(((1LL<<j)&i)==0||((1LL<<l)&i)==0)continue;
//cout<<i<<" "<<j<<" "<<l<<" "<<m<<endl;
rep(m,0,n+1){
if(m!=0&&j==0)continue;
if(m==0){
if(d(l,j)>=a||abs(k[l]-k[j])>=b){
if(m==l||j==m)continue;
if(dp[i^(1LL<<l)][m][j])chmax(dp[i][j][l],dp[i^(1LL<<l)][m][j]+1);
//print(m<<" "<<j<<" "<<l);
/* print(dp[i^(1LL<<m)][h][j][l]);
print((i^1LL<<m));*/
}
}
else if(d(l,j)+d(l,m)>=a||abs(k[l]-k[j])>=b){
if(m==l||j==m)continue;
if(dp[i^(1LL<<l)][m][j])chmax(dp[i][j][l],dp[i^(1LL<<l)][m][j]+1);
//print(m<<" "<<j<<" "<<l);
/* print(dp[i^(1LL<<m)][h][j][l]);
print((i^1LL<<m));*/
}
}
}
}
}
ll ans=0;
rep(i,0,(1LL<<c)){
rep(j,0,n+1){
rep(l,0,n+1){
chmax(ans,dp[i][j][l]);
}
}
}
print(ans);
}