結果

問題 No.1043 直列大学
ユーザー ptotq
提出日時 2020-05-01 22:17:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 258 ms / 2,000 ms
コード長 750 bytes
コンパイル時間 512 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 101,944 KB
最終ジャッジ日時 2024-12-22 19:32:09
合計ジャッジ時間 3,845 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
V = sorted(map(int, input().split()))
R = sorted(map(int, input().split()))
A, B = map(int, input().split())
mod = 10**9 + 7

V_max, R_max = sum(V), sum(R)
dp_v = [1] + [0]*V_max
subt = 0
for v in V:
    for i in range(subt, -1, -1):
        dp_v[i+v] += dp_v[i]
    subt += v

dp_r = [1] + [0]*R_max
subt = 0
for r in R:
    for i in range(subt, -1, -1):
        dp_r[i+r] += dp_r[i]
    subt += r

dp_r[0] = 0
for i in range(1, R_max):
    dp_r[i+1] += dp_r[i]
    dp_r[i+1] %= mod


ans = 0
for v in range(1, V_max+1):
    dp_v[v] %= mod
    # (lb, ub]
    lb, ub = (v+B-1)//B - 1, v//A
    if ub > R_max:
        ub = R_max

    if lb < ub:
        ans = (ans + dp_v[v] * (dp_r[ub] - dp_r[lb])) % mod

print(ans)
0