結果

問題 No.1043 直列大学
ユーザー rafi2rafi2
提出日時 2023-03-16 02:32:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,084 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 81,812 KB
実行使用メモリ 238,636 KB
最終ジャッジ日時 2023-10-18 12:47:29
合計ジャッジ時間 10,488 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,672 KB
testcase_01 AC 39 ms
53,672 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 39 ms
53,672 KB
testcase_05 AC 39 ms
53,672 KB
testcase_06 AC 39 ms
53,672 KB
testcase_07 WA -
testcase_08 AC 40 ms
53,672 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 502 ms
203,140 KB
testcase_15 AC 562 ms
224,524 KB
testcase_16 AC 460 ms
193,524 KB
testcase_17 AC 295 ms
140,760 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 161 ms
104,376 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

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 = ceil(i/a)
    l = i//b
#    print(l,r)
    if l >R:
        continue
    if r > R:
        x = seg2.fold(l,R)
    else:
        x = seg2.fold(l,r)
    if l == 0:
        x -= 1
#    print(x)
    ans += x*dp1[n][i]
    ans %= mod
print(ans)
0