#1160396 (C++23) No.3502 GCD Knapsack

• 問題: No.3502 GCD Knapsack
• ユーザー: zer0-star
• 提出日時: 2026-04-19 10:32:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 24 ms / 2,000 ms
• コード長: 5,115 bytes
• コンパイル時間: 9,364 ms
• コンパイル使用メモリ: 458,164 KB
• 実行使用メモリ: 8,192 KB
• 最終ジャッジ日時: 2026-04-19 10:55:11
• 合計ジャッジ時間: 16,564 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	AC * 3
other	AC * 35

ソースコード

#define USE_ACLIBRARY 0

#if __has_include("all.hpp") && 0

#include "all.hpp"

#else

#include <bits/extc++.h>

#if __has_include(<atcoder/all>) || USE_ACLIBRARY

#include <atcoder/all>

#endif

#endif

#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)

using ll = long long int;
using ull = unsigned long long int;

using pll = std::pair<ll, ll>;
using pil = std::pair<int, ll>;
using pli = std::pair<ll, int>;
using pii = std::pair<int, int>;

using namespace std::literals;

std::mt19937_64 rng{std::random_device()()};

template <class T>
bool chmin(T& x, const T& val) {
  if (x > val) {
    x = val;
    return true;
  } else {
    return false;
  }
}

template <class T>
bool chmin2(T& x, const T& val) {
  if (x < 0 || x > val) {
    x = val;
    return true;
  } else {
    return false;
  }
}

template <class T>
bool chmax(T& x, const T& val) {
  if (x < val) {
    x = val;
    return true;
  } else {
    return false;
  }
}

ll isqrt(ll n) {
  assert(n >= 0);
  if (n == 0) return 0;

  uint32_t c = (std::bit_width(uint64_t(n)) - 1) / 2;
  ll a = 1;
  ll d = 0;

  for (int s = std::bit_width(c) - 1; s >= 0; s--) {
    ll e = d;
    d = c >> s;
    a = (a << (d - e - 1)) + (n >> (2 * c - e - d + 1)) / a;
  }

  return a - (a * a > n);
}

#if __has_include(<atcoder/all>) || USE_ACLIBRARY

template <class mint, atcoder::internal::is_static_modint_t<mint>* = nullptr>
std::ostream& operator<<(std::ostream& os, const mint& v) {
  return os << v.val();
}

template <class mint, atcoder::internal::is_static_modint_t<mint>* = nullptr>
std::istream& operator>>(std::istream& is, mint& v) {
  int tmp;
  is >> tmp;
  v = tmp;
  return is;
}

#endif

template <class T, class U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
  return is >> p.first >> p.second;
}

template <class... T>
std::istream& operator>>(std::istream& is, std::tuple<T...>& tpl) {
  std::apply([&](auto&&... args) { (is >> ... >> args); }, tpl);
  return is;
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for (T& x : v) is >> x;
  return is;
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++)
    os << v[i] << (i == v.size() - 1 ? "" : " ");
  return os;
}

template <class I, class T>
std::vector<T> make_vector(I n, const T& x) {
  return std::vector<T>(n, x);
}

template <class I, class J, class K, class... Ts>
auto make_vector(I i, J j, K k, Ts&&... xs) {
  return std::vector(i, make_vector(j, k, xs...));
}

struct Initialization {
  Initialization() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
  }
} initialization;

constexpr const std::pair<int, int> DIRS[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

template <typename T>
using infs = std::numeric_limits<T>;

template <typename T>
class factorials {
 public:
  static size_t n;
  static std::vector<T> fact, inv_fact;

  static inline void extend(size_t m) {
    if (m <= n) return;
    fact.resize(m + 1);
    inv_fact.resize(m + 1);
    for (size_t i = n + 1; i <= m; i++) fact[i] = fact[i - 1] * i;
    inv_fact[m] = fact[m].inv();
    for (size_t i = m; i > n + 1; i--) inv_fact[i - 1] = inv_fact[i] * i;
    n = m;
  }

  static T inv(int k) {
    extend(k);
    return inv_fact[k];
  }

  static T get(int k) {
    extend(k);
    return fact[k];
  }

  static T perm(int n, int k) {
    if (n < k) return 0;
    if (k < 0) return 0;
    extend(n);
    return fact[n] * inv_fact[n - k];
  }

  static T choose(int n, int k) {
    if (n < k) return 0;
    if (k < 0) return 0;
    extend(n);
    return fact[n] * inv_fact[n - k] * inv_fact[k];
  }

  static T catalan(int n) { return get(2 * n) * inv(n + 1) * inv(n); }
};

template <typename T>
size_t factorials<T>::n = 0;

template <typename T>
std::vector<T> factorials<T>::fact = {1};

template <typename T>
std::vector<T> factorials<T>::inv_fact = {1};

#if __has_include(<atcoder/all>) || USE_ACLIBRARY

using mint = atcoder::modint998244353;
// using mint = atcoder::modint1000000007;

using fs = factorials<mint>;

#endif

template <typename T>
using pq_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;

namespace pbds = __gnu_pbds;

template <typename T>
using tree = pbds::tree<T, pbds::null_type, std::less<T>, pbds::rb_tree_tag,
                        pbds::tree_order_statistics_node_update>;

int main() {
  ll N, W;
  std::cin >> N >> W;
  std::vector<pll> XY(N);
  rep(i, N) {
    std::cin >> XY[i].first;
  }
  rep(i, N) {
    std::cin >> XY[i].second;
  }

  std::vector<ll> sums(200000 + 1);

  for (auto [x, y] : XY) {
    sums[x] += y;
  }

  rep(i, 1, 200001) {
    rep(k, i * 2, 200001, i) {
      sums[i] += sums[k];
    }
  }

  ll ans = 0;

  rep(i, W, 200001) {
    chmax(ans, sums[i]);
  }

  std::println("{}", ans);
}