結果

問題 No.1043 直列大学
ユーザー rafi2rafi2
提出日時 2023-03-16 08:51:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 805 ms / 2,000 ms
コード長 3,086 bytes
コンパイル時間 937 ms
コンパイル使用メモリ 81,576 KB
実行使用メモリ 236,856 KB
最終ジャッジ日時 2023-10-18 12:55:06
合計ジャッジ時間 10,466 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,536 KB
testcase_01 AC 39 ms
53,536 KB
testcase_02 AC 38 ms
53,536 KB
testcase_03 AC 38 ms
53,536 KB
testcase_04 AC 38 ms
53,536 KB
testcase_05 AC 39 ms
53,536 KB
testcase_06 AC 40 ms
53,536 KB
testcase_07 AC 38 ms
53,536 KB
testcase_08 AC 40 ms
53,536 KB
testcase_09 AC 132 ms
81,864 KB
testcase_10 AC 149 ms
90,068 KB
testcase_11 AC 422 ms
173,496 KB
testcase_12 AC 805 ms
236,856 KB
testcase_13 AC 482 ms
190,244 KB
testcase_14 AC 481 ms
201,944 KB
testcase_15 AC 544 ms
223,084 KB
testcase_16 AC 449 ms
193,348 KB
testcase_17 AC 285 ms
140,024 KB
testcase_18 AC 401 ms
141,356 KB
testcase_19 AC 529 ms
187,808 KB
testcase_20 AC 319 ms
138,000 KB
testcase_21 AC 487 ms
172,224 KB
testcase_22 AC 486 ms
175,560 KB
testcase_23 AC 644 ms
230,224 KB
testcase_24 AC 330 ms
152,260 KB
testcase_25 AC 424 ms
183,860 KB
testcase_26 AC 491 ms
201,820 KB
testcase_27 AC 161 ms
104,248 KB
testcase_28 AC 243 ms
118,136 KB
testcase_29 AC 106 ms
79,628 KB
testcase_30 AC 306 ms
143,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m = map(int,input().split())
v = list(map(int,input().split()))
r = list(map(int,input().split()))
a,b = map(int,input().split())
mod = 10**9+7

#dp,nmの配列
#dp[iコメまで選んでいい][j個選んだ]

#電流を追加するか？vi,rjが1000だから最大電流が1000*100で10**5か
#だとするとdp[][][電流]だと間に合わん

#なら電圧をもつか？抵抗を持つか？

#vとrの組み合わせは独立ってことに注意

#vだけやってV
#rだけやってR

#それでその候補ずつってのは？

##dp[iコメまで選んでいい][V]
V = max(v)*n+1
R = max(r)*m+1
dp1 = [[0]*(V) for _ in range(n+1)]
dp2 = [[0]*(R) for _ in range(m+1)]
dp1[0][0] = 1
dp2[0][0] = 1
for i in range(n):
    for j in range(V-1):
        dp1[i+1][j] += dp1[i][j]
        dp1[i+1][j]%=mod
#        print(i+1,j+v[i])
        if j+v[i] < V:
#            print(j+v[i])
            dp1[i+1][j+v[i]] += dp1[i][j]
            dp1[i+1][j+v[i]] %= mod

for i in range(m):
    for j in range(R-1):
        dp2[i+1][j] += dp2[i][j]
        dp2[i+1][j] %= mod
        if j+r[i] < R:
            dp2[i+1][j+r[i]] += dp2[i][j]
            dp2[i+1][j+r[i]] %= mod
#A<= v/r <=B
#v固定r小さすぎるとでかい、デカすぎるとA下回る
#にぶたんでseg木？

#非再帰 SegTree

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


#X_fとX_unit変えることに注意

#開区間
#0-indexed
#a0,a1,a2,...
#ベースの1-indexed

class SegTree:
    X_unit = 0#モノイドの単位元
    X_f = sum

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N) #

    def build(self, seq):
        for i, x in enumerate(seq, self.N):#indexの番号、要素の順に取得できる
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):#-1個飛ばしに
            self.X[i] = self.X_f([self.X[i << 1], self.X[i << 1 | 1]])# | 1 は１を足してるだけ

    def set_val(self, i, x):
        i += self.N #初期値はNからスタートするので
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f([self.X[i << 1], self.X[i << 1 | 1]])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f([vL, self.X[L]])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f([self.X[R], vR])
            L >>= 1
            R >>= 1
        return self.X_f([vL, vR])
#seg1 = SegTree(V)
#seg1.build(dp1[n])
seg2 = SegTree(R)
seg2.build(dp2[m])

#print(dp2[m])
#print(R)


ans = 0
#print(dp1[n])
#print(dp2[m])
from math import ceil
for i in range(1,V):
    if dp1[n][i] == 0:
        continue
    r = i//a
    l = ceil(i/b)
#    print(l,r)
    if l >R:
        continue
    if r >= R:
        x = seg2.fold(l,R)
    else:
        x = seg2.fold(l,r+1)
    if l == 0:
        x -= 1
#   print(x)
    ans += x*dp1[n][i]
    ans %= mod
print(ans)
0