結果

問題 No.3502 GCD Knapsack
コンテスト
ユーザー useless
提出日時 2026-04-18 20:37:41
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 724 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 254 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 628,212 KB
最終ジャッジ日時 2026-04-18 20:38:28
合計ジャッジ時間 7,773 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd
def divisors(x):
  ret = []
  i = 1
  while (i**2 <= x):
    if x%i == 0:
      ret.append(i)
      if i != x//i:
        ret.append(x//i)
    i += 1
  return sorted(ret)

n,w = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

d = []
for xi in x:
	d += divisors(xi)
ss = sorted(set(d))
d0 = {v:i for i,v in enumerate(ss)}
d1 = {i:v for i,v in enumerate(ss)}

dp = [0 for _ in range(len(ss))]
for xi,yi in zip(x,y):
	ndp = [0 for _ in range(len(ss))]
	for i in range(len(ss)):
		ndp[i] = max(dp[i],ndp[i])
		ni = d0[gcd(xi,d1[i])]
		ndp[ni] = max(dp[i]+yi,ndp[ni])
	dp = ndp
ans = 0
for i in range(len(ss)):
	if d1[i] >= w:
		ans = max(dp[i],ans)
print(ans)
0