結果
問題 |
No.1043 直列大学
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)