結果

問題 No.1043 直列大学
コンテスト
ユーザー rafi2
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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