結果

問題 No.1043 直列大学
ユーザー rafi2rafi2
提出日時 2023-03-16 08:51:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 713 ms / 2,000 ms
コード長 3,086 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 237,336 KB
最終ジャッジ日時 2024-09-18 09:15:17
合計ジャッジ時間 10,006 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
52,992 KB
testcase_01 AC 36 ms
52,708 KB
testcase_02 AC 37 ms
52,736 KB
testcase_03 AC 35 ms
53,120 KB
testcase_04 AC 34 ms
53,248 KB
testcase_05 AC 35 ms
52,992 KB
testcase_06 AC 39 ms
52,744 KB
testcase_07 AC 34 ms
52,864 KB
testcase_08 AC 35 ms
52,992 KB
testcase_09 AC 116 ms
82,608 KB
testcase_10 AC 132 ms
90,852 KB
testcase_11 AC 387 ms
174,212 KB
testcase_12 AC 713 ms
237,336 KB
testcase_13 AC 433 ms
191,456 KB
testcase_14 AC 451 ms
202,348 KB
testcase_15 AC 502 ms
223,568 KB
testcase_16 AC 404 ms
193,804 KB
testcase_17 AC 256 ms
140,400 KB
testcase_18 AC 377 ms
141,604 KB
testcase_19 AC 475 ms
187,944 KB
testcase_20 AC 297 ms
138,004 KB
testcase_21 AC 434 ms
172,552 KB
testcase_22 AC 432 ms
176,364 KB
testcase_23 AC 616 ms
230,828 KB
testcase_24 AC 340 ms
153,092 KB
testcase_25 AC 397 ms
183,928 KB
testcase_26 AC 444 ms
202,300 KB
testcase_27 AC 146 ms
104,620 KB
testcase_28 AC 219 ms
118,964 KB
testcase_29 AC 91 ms
79,780 KB
testcase_30 AC 272 ms
143,872 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