結果

問題 No.1043 直列大学
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-05-01 22:28:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 813 ms / 2,000 ms
コード長 1,350 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 259,120 KB
最終ジャッジ日時 2024-06-02 02:56:52
合計ジャッジ時間 10,683 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
53,384 KB
testcase_01 AC 35 ms
53,260 KB
testcase_02 AC 33 ms
54,612 KB
testcase_03 AC 33 ms
53,504 KB
testcase_04 AC 33 ms
52,992 KB
testcase_05 AC 33 ms
52,652 KB
testcase_06 AC 33 ms
53,684 KB
testcase_07 AC 34 ms
53,568 KB
testcase_08 AC 33 ms
53,216 KB
testcase_09 AC 79 ms
76,744 KB
testcase_10 AC 95 ms
77,308 KB
testcase_11 AC 96 ms
77,832 KB
testcase_12 AC 813 ms
259,120 KB
testcase_13 AC 497 ms
172,976 KB
testcase_14 AC 577 ms
182,848 KB
testcase_15 AC 694 ms
203,936 KB
testcase_16 AC 539 ms
175,196 KB
testcase_17 AC 301 ms
126,244 KB
testcase_18 AC 303 ms
116,828 KB
testcase_19 AC 537 ms
168,952 KB
testcase_20 AC 305 ms
122,316 KB
testcase_21 AC 464 ms
157,764 KB
testcase_22 AC 474 ms
163,892 KB
testcase_23 AC 741 ms
215,760 KB
testcase_24 AC 370 ms
131,344 KB
testcase_25 AC 509 ms
164,780 KB
testcase_26 AC 560 ms
175,884 KB
testcase_27 AC 229 ms
113,892 KB
testcase_28 AC 346 ms
139,716 KB
testcase_29 AC 70 ms
77,588 KB
testcase_30 AC 529 ms
190,236 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