結果

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

ソースコード

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 最後の数の連続数
"""
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] = sum([sum(v) for v in DP[allsum-last-1]])
                try:
                    DP[allsum][last][length] -= sum(DP[allsum-last-1][last])
                except IndexError:
                    pass
                DP[allsum][last][length] %= mod

ans = 0
for i in range(L-1, R):
    ans += sum([sum(v) for v in DP[i]])
print(ans%mod)
#print(DP)
0