結果

問題 No.1043 直列大学
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-05-01 22:28:06
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 990 ms / 2,000 ms
コード長 1,350 bytes
コンパイル時間 611 ms
コンパイル使用メモリ 86,628 KB
実行使用メモリ 258,052 KB
最終ジャッジ日時 2023-08-24 05:49:26
合計ジャッジ時間 14,130 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
71,280 KB
testcase_01 AC 75 ms
71,024 KB
testcase_02 AC 76 ms
71,132 KB
testcase_03 AC 76 ms
71,260 KB
testcase_04 AC 84 ms
71,304 KB
testcase_05 AC 75 ms
71,152 KB
testcase_06 AC 76 ms
71,284 KB
testcase_07 AC 75 ms
71,172 KB
testcase_08 AC 75 ms
71,024 KB
testcase_09 AC 124 ms
77,640 KB
testcase_10 AC 145 ms
79,416 KB
testcase_11 AC 140 ms
78,448 KB
testcase_12 AC 990 ms
258,052 KB
testcase_13 AC 647 ms
171,852 KB
testcase_14 AC 728 ms
184,912 KB
testcase_15 AC 877 ms
210,172 KB
testcase_16 AC 676 ms
172,636 KB
testcase_17 AC 382 ms
129,048 KB
testcase_18 AC 383 ms
118,200 KB
testcase_19 AC 643 ms
167,200 KB
testcase_20 AC 375 ms
122,416 KB
testcase_21 AC 557 ms
157,484 KB
testcase_22 AC 590 ms
164,204 KB
testcase_23 AC 912 ms
217,344 KB
testcase_24 AC 459 ms
132,440 KB
testcase_25 AC 626 ms
163,596 KB
testcase_26 AC 715 ms
176,252 KB
testcase_27 AC 303 ms
116,768 KB
testcase_28 AC 433 ms
139,700 KB
testcase_29 AC 109 ms
78,624 KB
testcase_30 AC 660 ms
189,064 KB
権限があれば一括ダウンロードができます

ソースコード

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
    ans %= mod

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