結果

問題 No.1043 直列大学
ユーザー 👑 SPD_9X2
提出日時 2020-05-01 22:26:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,328 bytes
コンパイル時間 396 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 258,480 KB
最終ジャッジ日時 2024-12-25 13:01:05
合計ジャッジ時間 15,359 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

作れる抵抗を全列挙
& 作れる電圧を全列挙
累積和でその範囲にいくつあるか調べる
かな

"""
import bisect
mod = 10**9+7

N,M = map(int,input().split())

V = list(map(int,input().split()))
R = list(map(int,input().split()))

A,B = map(int,input().split())

Vdic = {}
Vdic[0] = 1
vs = [0]

for i in range(N):

    nv = V[i]
    pool = []

    for j in Vdic:
        pool.append( [j+nv , Vdic[j] ])
    for x in pool:

        if x[0] not in Vdic:
            Vdic[x[0]] = 0
            vs.append(x[0])
        Vdic[x[0]] += x[1]
        Vdic[x[0]] %= mod
    
vs.append(-1)
vs.sort()
os = [0]

for i in range(1,len(vs)):
    os.append(os[-1] + Vdic[vs[i]])
    if vs[i] == 0:
        os[-1] = 0

Rdic = {}
Rdic[0] = 1
rs = [0]

for i in range(M):

    nr = R[i]
    pool = []

    for j in Rdic:
        pool.append( [j+nr , Rdic[j] ])
    for x in pool:

        if x[0] not in Rdic:
            Rdic[x[0]] = 0
            rs.append(x[0])
        Rdic[x[0]] += x[1]
        Rdic[x[0]] %= mod
ans = 0
for r in Rdic:

    if r <= 0:
        continue

    rlim = r*B
    llim = r*A

    lind = bisect.bisect_left(vs,llim) - 1
    rind = bisect.bisect_right(vs,rlim) - 1

    #print (r,Rdic[r],lind,rind)

    ans += Rdic[r] * (os[rind] - os[lind]) % mod

#print (vs,rs)
#print (os)
print (ans)
0