結果

問題 No.1353 Limited Sequence
コンテスト
ユーザー GER_chen
提出日時 2021-01-17 14:42:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,653 ms / 2,000 ms
コード長 1,276 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 350,440 KB
最終ジャッジ日時 2024-11-29 16:18:01
合計ジャッジ時間 33,586 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#1353
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
DP = [[[0]*((allsum+1)//(last+1)) for last in range(min(N, allsum+1))] for allsum in range(R)]
"""
allsum+1 総和
last+1 最後の数 <= 総和
length+1 最後の数の連続数
"""
DP1 = [[0 for last in range(min(N, allsum+1))] for allsum in range(R)]
DP2 = [0]*R

for allsum in range(R):
    for last in range(min(N, allsum+1)):
        for length in range((allsum+1)//(last+1)):
            if allsum == last and length == 0:
                DP[allsum][last][length] = 1
                #print(DP)
            elif length > 0:
                if allsum+1 >= 2*last+1:
                    if A[last] >= length+1:
                        DP[allsum][last][length] = DP[allsum-last-1][last][length-1]
            else:
                DP[allsum][last][length] = DP2[allsum-last-1]
                try:
                    DP[allsum][last][length] -= DP1[allsum-last-1][last]
                except IndexError:
                    pass
            DP[allsum][last][length] %= mod
            DP1[allsum][last] += DP[allsum][last][length]
            DP2[allsum] += DP[allsum][last][length]
        DP1[allsum][last] %= mod
    DP2[allsum] %= mod

ans = sum(DP2[L-1:R])
print(ans%mod)
0