結果

問題 No.1043 直列大学
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-05-01 22:26:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,328 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 259,372 KB
最終ジャッジ日時 2024-06-07 10:45:23
合計ジャッジ時間 12,321 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,696 KB
testcase_01 AC 37 ms
53,136 KB
testcase_02 AC 38 ms
53,540 KB
testcase_03 AC 38 ms
53,100 KB
testcase_04 AC 38 ms
52,812 KB
testcase_05 AC 37 ms
52,680 KB
testcase_06 AC 39 ms
52,520 KB
testcase_07 AC 39 ms
54,156 KB
testcase_08 AC 38 ms
53,068 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 596 ms
173,236 KB
testcase_14 AC 686 ms
182,748 KB
testcase_15 AC 834 ms
204,060 KB
testcase_16 AC 644 ms
175,036 KB
testcase_17 AC 366 ms
126,116 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 254 ms
114,196 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