結果
問題 |
No.1043 直列大学
|
ユーザー |
|
提出日時 | 2021-01-17 23:31:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 907 ms / 2,000 ms |
コード長 | 1,587 bytes |
コンパイル時間 | 298 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 367,152 KB |
最終ジャッジ日時 | 2024-12-22 20:13:52 |
合計ジャッジ時間 | 10,602 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#region Header #!/usr/bin/env python3 # from typing import * import sys import io import math import collections import decimal import itertools from queue import PriorityQueue import bisect import heapq def input(): return sys.stdin.readline()[:-1] sys.setrecursionlimit(1000000) #endregion # _INPUT = """3 3 # 2 3 4 # 10 23 26 # 1 100 # """ # sys.stdin = io.StringIO(_INPUT) MOD = 1000000007 def main(): N, M = map(int, input().split()) V = list(map(int, input().split())) R = list(map(int, input().split())) A, B = map(int, input().split()) SumV = sum(V) dpV = [[0 for _ in range(SumV+1)] for _ in range(N)] dpV[0][0] = 1 dpV[0][V[0]] = 1 for i in range(0, N-1): for v in range(SumV+1): if dpV[i][v] > 0: dpV[i+1][v] += dpV[i][v] dpV[i+1][v+V[i+1]] += dpV[i][v] SumR = sum(R) dpR = [[0 for _ in range(SumR+1)] for _ in range(M)] dpR[0][0] = 1 dpR[0][R[0]] = 1 for i in range(0, M-1): for r in range(SumR+1): if dpR[i][r] > 0: dpR[i+1][r] += dpR[i][r] dpR[i+1][r+R[i+1]] += dpR[i][r] SV = [0 for _ in range(SumV+1)] SV[0] = dpV[N-1][0] for v in range(1, SumV+1): SV[v] = SV[v-1] + dpV[N-1][v] n = 0 for r in range(1, SumR+1): v1 = max(r*A, 1) v2 = min(r*B, SumV) if v1 <= v2: n += dpR[M-1][r] * (SV[v2] - SV[v1-1]) print(n % MOD) if __name__ == '__main__': main()