結果
問題 | No.1043 直列大学 |
ユーザー | McGregorsh |
提出日時 | 2023-07-12 12:36:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 708 ms / 2,000 ms |
コード長 | 2,261 bytes |
コンパイル時間 | 515 ms |
コンパイル使用メモリ | 86,740 KB |
実行使用メモリ | 256,804 KB |
最終ジャッジ日時 | 2023-10-12 02:46:15 |
合計ジャッジ時間 | 19,022 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 284 ms
103,984 KB |
testcase_01 | AC | 276 ms
100,100 KB |
testcase_02 | AC | 300 ms
107,460 KB |
testcase_03 | AC | 277 ms
100,020 KB |
testcase_04 | AC | 276 ms
100,096 KB |
testcase_05 | AC | 282 ms
101,244 KB |
testcase_06 | AC | 281 ms
101,472 KB |
testcase_07 | AC | 286 ms
103,028 KB |
testcase_08 | AC | 294 ms
104,688 KB |
testcase_09 | AC | 499 ms
178,212 KB |
testcase_10 | AC | 538 ms
193,952 KB |
testcase_11 | AC | 673 ms
243,284 KB |
testcase_12 | AC | 708 ms
256,804 KB |
testcase_13 | AC | 633 ms
230,252 KB |
testcase_14 | AC | 650 ms
237,912 KB |
testcase_15 | AC | 692 ms
251,104 KB |
testcase_16 | AC | 641 ms
234,980 KB |
testcase_17 | AC | 548 ms
197,984 KB |
testcase_18 | AC | 554 ms
199,096 KB |
testcase_19 | AC | 627 ms
228,108 KB |
testcase_20 | AC | 546 ms
196,912 KB |
testcase_21 | AC | 604 ms
218,020 KB |
testcase_22 | AC | 616 ms
222,884 KB |
testcase_23 | AC | 703 ms
256,428 KB |
testcase_24 | AC | 577 ms
208,084 KB |
testcase_25 | AC | 628 ms
228,308 KB |
testcase_26 | AC | 657 ms
237,544 KB |
testcase_27 | AC | 469 ms
166,568 KB |
testcase_28 | AC | 631 ms
227,556 KB |
testcase_29 | AC | 397 ms
139,992 KB |
testcase_30 | AC | 544 ms
195,432 KB |
ソースコード
import sys from sys import stdin from fractions import Fraction import math from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from decimal import Decimal, getcontext, ROUND_HALF_UP def i_input(): return int(stdin.readline()) def i_map(): return map(int, stdin.readline().split()) def i_list(): return list(i_map()) def s_input(): return stdin.readline()[:-1] def s_map(): return s_input().split() def s_list(): return list(s_map()) def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 alpa = 'abcdefghijklmnopqrstuvwxyz' ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' def main(): N, M = i_map() V = i_list() R = i_list() A, B = i_map() dp1 = [[0] * 100001 for i in range(N+1)] dp1[0][0] = 1 for i in range(N): for j in range(100001): if j + V[i] <= 100000: dp1[i+1][j+V[i]] += dp1[i][j] dp1[i+1][j+V[i]] %= MOD dp1[i+1][j] += dp1[i][j] dp1[i+1][j] %= MOD dp2 = [[0] * 100001 for i in range(M+1)] dp2[0][0] = 1 for i in range(M): for j in range(100001): if j + R[i] <= 100000: dp2[i+1][j+R[i]] += dp2[i][j] dp2[i+1][j+R[i]] %= MOD dp2[i+1][j] += dp2[i][j] dp2[i+1][j] %= MOD score = dp1[-1] AS = [score[0]] for i in range(1, 100001): nxt = AS[-1] + score[i] nxt %= MOD AS.append(nxt) ans = 0 for i in range(100001): L = min(100000, max(0, i * A-1)) R = min(100000, i * B) cost = AS[R] - AS[L] cost %= MOD cost *= dp2[-1][i] cost %= MOD ans += cost ans %= MOD print(ans) if __name__ == '__main__': main()