結果

問題 No.2375 watasou and hibit's baseball
ユーザー watasou1543watasou1543
提出日時 2023-06-21 06:50:48
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 13,115 bytes
コンパイル時間 7,238 ms
コンパイル使用メモリ 173,312 KB
実行使用メモリ 61,196 KB
最終ジャッジ日時 2024-07-08 08:44:10
合計ジャッジ時間 10,494 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 WA -
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 91 ms
28,508 KB
testcase_04 WA -
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 270 ms
61,056 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 WA -
testcase_09 AC 1 ms
5,376 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 212 ms
61,056 KB
testcase_13 AC 85 ms
28,544 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 19 ms
8,064 KB
testcase_16 AC 9 ms
5,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 2 ms
5,376 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 222 ms
60,928 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 227 ms
60,928 KB
testcase_34 WA -
testcase_35 AC 236 ms
61,056 KB
testcase_36 AC 231 ms
61,056 KB
testcase_37 AC 193 ms
60,928 KB
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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,0,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(d(j,m)+d(l,m)>=a||abs(k[m]-k[l])>=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(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);
}
0