結果

問題 No.1043 直列大学
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-05-01 22:26:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,328 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 87,392 KB
実行使用メモリ 258,432 KB
最終ジャッジ日時 2023-08-26 15:07:43
合計ジャッジ時間 13,063 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
71,280 KB
testcase_01 AC 72 ms
71,296 KB
testcase_02 AC 72 ms
71,252 KB
testcase_03 AC 72 ms
71,204 KB
testcase_04 AC 75 ms
71,284 KB
testcase_05 AC 72 ms
71,180 KB
testcase_06 AC 72 ms
71,232 KB
testcase_07 AC 71 ms
71,160 KB
testcase_08 AC 70 ms
71,200 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 598 ms
172,088 KB
testcase_14 AC 589 ms
185,068 KB
testcase_15 AC 715 ms
210,152 KB
testcase_16 AC 558 ms
172,356 KB
testcase_17 AC 332 ms
128,948 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 250 ms
116,500 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

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