結果
問題 | No.1043 直列大学 |
ユーザー |
|
提出日時 | 2020-05-01 21:48:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 1,072 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 67,584 KB |
最終ジャッジ日時 | 2024-12-22 19:25:31 |
合計ジャッジ時間 | 4,660 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
MOD = 10 ** 9 + 7 INF = 10 ** 10 import sys sys.setrecursionlimit(100000000) from bisect import bisect_left,bisect_right def main(): n,m = map(int,input().split()) Volt = list(map(int,input().split())) Regist = list(map(int,input().split())) a,b = map(int,input().split()) MAX = 100000 dp1 = [1] + [0] * MAX for v in Volt: for j in range(MAX,0,-1): dp1[j] = dp1[j] if j - v >= 0: dp1[j] += dp1[j - v] dp1[j] %= MOD for i in range(1,MAX + 1): dp1[i] += dp1[i - 1] dp1[i] %= MOD dp2 = [1] + [0] * MAX for r in Regist: for j in range(MAX,0,-1): dp2[j] = dp2[j] if j - r >= 0: dp2[j] += dp2[j - r] dp2[j] %= MOD ans = 0 for r in range(1,MAX + 1): if b*r <= MAX: ans += (dp1[b*r] - dp1[a*r - 1])*dp2[r] elif a*r - 1 <= MAX: ans += (dp1[-1] - dp1[a*r - 1])*dp2[r] ans %= MOD print(ans) if __name__ == '__main__': main()