結果
問題 | No.1353 Limited Sequence |
ユーザー | GER_chen |
提出日時 | 2021-01-17 14:42:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,615 ms / 2,000 ms |
コード長 | 1,276 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 82,520 KB |
実行使用メモリ | 350,640 KB |
最終ジャッジ日時 | 2024-05-07 03:42:23 |
合計ジャッジ時間 | 32,395 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
51,968 KB |
testcase_01 | AC | 58 ms
66,816 KB |
testcase_02 | AC | 62 ms
69,504 KB |
testcase_03 | AC | 47 ms
61,568 KB |
testcase_04 | AC | 51 ms
63,904 KB |
testcase_05 | AC | 52 ms
64,384 KB |
testcase_06 | AC | 57 ms
65,152 KB |
testcase_07 | AC | 59 ms
68,608 KB |
testcase_08 | AC | 58 ms
68,608 KB |
testcase_09 | AC | 63 ms
68,480 KB |
testcase_10 | AC | 60 ms
68,480 KB |
testcase_11 | AC | 55 ms
65,280 KB |
testcase_12 | AC | 910 ms
241,128 KB |
testcase_13 | AC | 1,006 ms
251,540 KB |
testcase_14 | AC | 168 ms
100,780 KB |
testcase_15 | AC | 436 ms
158,320 KB |
testcase_16 | AC | 93 ms
83,288 KB |
testcase_17 | AC | 112 ms
86,784 KB |
testcase_18 | AC | 887 ms
238,320 KB |
testcase_19 | AC | 1,115 ms
273,012 KB |
testcase_20 | AC | 303 ms
128,788 KB |
testcase_21 | AC | 154 ms
94,208 KB |
testcase_22 | AC | 137 ms
92,160 KB |
testcase_23 | AC | 883 ms
233,344 KB |
testcase_24 | AC | 656 ms
189,532 KB |
testcase_25 | AC | 984 ms
260,228 KB |
testcase_26 | AC | 542 ms
175,188 KB |
testcase_27 | AC | 389 ms
141,440 KB |
testcase_28 | AC | 215 ms
109,788 KB |
testcase_29 | AC | 309 ms
126,336 KB |
testcase_30 | AC | 821 ms
217,344 KB |
testcase_31 | AC | 537 ms
166,948 KB |
testcase_32 | AC | 493 ms
202,692 KB |
testcase_33 | AC | 142 ms
99,628 KB |
testcase_34 | AC | 985 ms
311,420 KB |
testcase_35 | AC | 321 ms
151,168 KB |
testcase_36 | AC | 445 ms
183,040 KB |
testcase_37 | AC | 1,598 ms
350,276 KB |
testcase_38 | AC | 1,603 ms
350,640 KB |
testcase_39 | AC | 1,604 ms
350,408 KB |
testcase_40 | AC | 1,591 ms
350,384 KB |
testcase_41 | AC | 1,597 ms
350,304 KB |
testcase_42 | AC | 1,597 ms
350,524 KB |
testcase_43 | AC | 1,606 ms
350,180 KB |
testcase_44 | AC | 1,585 ms
350,608 KB |
testcase_45 | AC | 1,602 ms
350,228 KB |
testcase_46 | AC | 1,615 ms
350,524 KB |
testcase_47 | AC | 1,133 ms
350,188 KB |
ソースコード
#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)