#1178428 (C++23) No.3634 Made to order

• 問題: No.3634 Made to order
• ユーザー: Kude
• 提出日時: 2026-08-22 15:35:33
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 615 ms / 2,000 ms
• コード長: 2,561 bytes
• コンパイル時間: 3,168 ms
• コンパイル使用メモリ: 364,908 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-22 15:35:46
• 合計ジャッジ時間: 11,150 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

サブタスク	配点	結果
サブタスク $1$	20 %	AC * 8
サブタスク $2$	10 %	AC * 21
サブタスク $3$	70 %	AC * 26
合計	3 * 100% = 300 点

ソースコード

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
constexpr int INF = 1001001001;

struct enum_k_bits {
  int n2, k, s;
  enum_k_bits(int n, int k) : n2(1 << n), k(k), s((1 << k) - 1) {}
  enum_k_bits begin() { return *this; }
  int end() const { return n2; }
  int& operator*() { return s; }
  enum_k_bits& operator++() {
    if (k == 0) {
      s = n2;
    } else {
      int x = s & -s;
      int y = s + x;
      s = (((s & ~y) / x) >> 1) | y;
    }
    return *this;
  }
  bool operator!=(int ub) const { return s < ub; }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, d;
  cin >> n >> d;
  chmin(d, 1500);
  VI a(n), b(n), c(n);
  rep(i, n) cin >> a[i] >> b[i] >> c[i];
  segtree<int, [](int x, int y) { return min(x, y); }, []() { return INF; }> seg(d + 1);
  bool ans = false;
  for (int s : enum_k_bits(n, n / 2)) {
    VI idx;
    struct S { int x, y, z; };
    vector<S> p1, p2;
    VI idx1, idx2;
    rep(i, n) (s >> i & 1 ? idx1 : idx2).emplace_back(i);
    do {
      int x = 0, y = 0, z = 0;
      for (int i : idx1) {
        x = x + a[i];
        y = max(x, y) + b[i];
        z = max(y, z) + c[i];
      }
      if (z <= d) p1.emplace_back(x, y, z);
    } while (next_permutation(all(idx1)));
    do {
      int x = d, y = d, z = d;
      for (int i : idx2) {
        z = z - c[i];
        y = min(z, y) - b[i];
        x = min(y, x) - a[i];
      }
      if (x >= 0) p2.emplace_back(x, y, z);
    } while (next_permutation(all(idx2)));
    ranges::sort(p1, {}, &S::x);
    ranges::sort(p2, {}, &S::x);
    int ptr = 0;
    for (auto [x2, y2, z2] : p2) {
      while (ptr < ssize(p1) && p1[ptr].x <= x2) {
        auto [x1, y1, z1] = p1[ptr++];
        seg.set(y1, min(seg.get(y1), z1));
      }
      ans |= seg.prod(0, y2 + 1) <= z2;
    }
    for (auto [x1, y1, z1] : p1) seg.set(y1, INF);
  }
  cout << (ans ? "Yes\n" : "No\n");
}