結果
問題 | No.1043 直列大学 |
ユーザー | tcltk |
提出日時 | 2021-01-17 23:31:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,087 ms / 2,000 ms |
コード長 | 1,587 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 86,748 KB |
実行使用メモリ | 378,112 KB |
最終ジャッジ日時 | 2023-08-24 12:55:09 |
合計ジャッジ時間 | 14,769 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 235 ms
83,108 KB |
testcase_01 | AC | 238 ms
83,164 KB |
testcase_02 | AC | 233 ms
83,324 KB |
testcase_03 | AC | 234 ms
83,104 KB |
testcase_04 | AC | 233 ms
83,248 KB |
testcase_05 | AC | 235 ms
83,148 KB |
testcase_06 | AC | 234 ms
83,240 KB |
testcase_07 | AC | 234 ms
83,320 KB |
testcase_08 | AC | 239 ms
83,188 KB |
testcase_09 | AC | 256 ms
88,324 KB |
testcase_10 | AC | 270 ms
90,672 KB |
testcase_11 | AC | 407 ms
156,164 KB |
testcase_12 | AC | 1,087 ms
378,112 KB |
testcase_13 | AC | 545 ms
201,964 KB |
testcase_14 | AC | 582 ms
211,972 KB |
testcase_15 | AC | 719 ms
267,856 KB |
testcase_16 | AC | 532 ms
189,512 KB |
testcase_17 | AC | 323 ms
116,740 KB |
testcase_18 | AC | 335 ms
117,044 KB |
testcase_19 | AC | 531 ms
197,196 KB |
testcase_20 | AC | 320 ms
112,872 KB |
testcase_21 | AC | 481 ms
173,104 KB |
testcase_22 | AC | 480 ms
173,232 KB |
testcase_23 | AC | 770 ms
280,160 KB |
testcase_24 | AC | 383 ms
124,692 KB |
testcase_25 | AC | 487 ms
169,920 KB |
testcase_26 | AC | 578 ms
210,324 KB |
testcase_27 | AC | 294 ms
104,336 KB |
testcase_28 | AC | 345 ms
119,032 KB |
testcase_29 | AC | 257 ms
88,244 KB |
testcase_30 | AC | 514 ms
190,324 KB |
ソースコード
#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()