結果

問題 No.1043 直列大学
ユーザー lam6er
提出日時 2025-03-20 21:03:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 1,859 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 93,380 KB
最終ジャッジ日時 2025-03-20 21:03:39
合計ジャッジ時間 3,540 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

# Read input
N, M = map(int, input().split())
V = list(map(int, input().split()))
R = list(map(int, input().split()))
A, B = map(int, input().split())

# Calculate all possible non-empty subsets sum for dry cells (V)
sum_v_all = sum(V)
dp_v = [0] * (sum_v_all + 1)
dp_v[0] = 1
for v in V:
    for s in range(sum_v_all, v-1, -1):
        dp_v[s] = (dp_v[s] + dp_v[s - v]) % MOD

# Collect non-empty subsets for V
count_v = {}
for s in range(1, sum_v_all + 1):
    if dp_v[s] > 0:
        count_v[s] = dp_v[s]

# Calculate all possible non-empty subsets sum for light bulbs (R)
sum_r_all = sum(R)
dp_r = [0] * (sum_r_all + 1)
dp_r[0] = 1
for r in R:
    for s in range(sum_r_all, r-1, -1):
        dp_r[s] = (dp_r[s] + dp_r[s - r]) % MOD

# Collect non-empty subsets for R
count_r = {}
for s in range(1, sum_r_all + 1):
    if dp_r[s] > 0:
        count_r[s] = dp_r[s]

# Create cumulative sum array for R
max_r = sum_r_all
cumsum_r = [0] * (max_r + 2)  # cumsum_r[0] = 0 ... cumsum_r[max_r + 1] is for overflow
current_sum = 0
for s in range(0, max_r + 2):
    if s <= max_r and s in count_r:
        current_sum = (current_sum + count_r[s]) % MOD
    cumsum_r[s] = current_sum

total = 0

# Iterate over all possible voltage sums and check valid resistance sums
for sum_v, cnt_v in count_v.items():
    upper = sum_v // A
    if upper < 1:
        continue  # sum_r must be >=1, and upper is <1
    
    lower = (sum_v + B - 1) // B  # ceil(sum_v / B)
    if lower > upper:
        continue  # no valid range
    
    actual_upper = min(upper, max_r)
    if actual_upper < lower:
        continue
    
    # Calculate the count of resistance sums in [lower, actual_upper]
    cnt_r = (cumsum_r[actual_upper] - cumsum_r[lower - 1]) % MOD
    if cnt_r < 0:
        cnt_r += MOD
    
    total = (total + cnt_v * cnt_r) % MOD

print(total % MOD)
0