提出 #58017291

ソースコード 拡げる

P = 998244353
(N,M,K),*XY = $<.map{|ln| ln.split.map(&:to_i) }
V = [1,*XY.flatten].uniq.sort
E = V.each_cons(2).map.with_index{|(v0,v1),j| [v1-v0,nil,j] }<<[N+1-V[-1],nil,V.size-1]
E.rotate!(-1)
XY.each{|xy|
	i,j = xy.map{|v| V.index v }
	(E[j][1]||=[])<<i
}
D = [[1,*[0]*(V.size-1)]]
1.upto(K){|k| # (k-1,is),(k-d,j-1) -> (k,j)
	D<<E.map{|d,is,j0|
		dj = 0
		dj += D[-1].values_at(*is).sum%P if is
		dj += D[-d][j0] if d<=k
		dj %= P
	}
}
p (D[K].sum+E.sum{|d,_,j0| D[-d..-2].sum{|dk| dk[j0] }%P })%P

提出情報

提出日時
問題 F - Teleporting Takahashi 2
ユーザ ds14050
言語 Ruby (ruby 3.2.2)
得点 0
コード長 521 Byte
結果 TLE
実行時間 3321 ms
メモリ 192352 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 525
結果
AC × 3
AC × 41
TLE × 12
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 97 ms 17092 KiB
00_sample_01.txt AC 80 ms 27572 KiB
00_sample_02.txt AC 48 ms 17768 KiB
01_random_00.txt AC 43 ms 17584 KiB
01_random_01.txt AC 45 ms 17452 KiB
01_random_02.txt AC 44 ms 17548 KiB
01_random_03.txt AC 49 ms 17864 KiB
01_random_04.txt AC 2752 ms 141708 KiB
01_random_05.txt AC 2248 ms 118908 KiB
01_random_06.txt AC 2092 ms 116348 KiB
01_random_07.txt AC 2126 ms 113404 KiB
01_random_08.txt TLE 3319 ms 160856 KiB
01_random_09.txt TLE 3319 ms 165044 KiB
01_random_10.txt TLE 3319 ms 164164 KiB
01_random_11.txt TLE 3319 ms 165036 KiB
01_random_12.txt TLE 3319 ms 164108 KiB
01_random_13.txt AC 737 ms 52648 KiB
01_random_14.txt AC 730 ms 52940 KiB
01_random_15.txt AC 732 ms 52708 KiB
01_random_16.txt AC 2774 ms 148512 KiB
01_random_17.txt AC 2738 ms 148496 KiB
01_random_18.txt AC 2786 ms 148420 KiB
01_random_19.txt AC 2956 ms 183316 KiB
01_random_20.txt AC 2917 ms 183456 KiB
01_random_21.txt AC 2916 ms 180064 KiB
01_random_22.txt TLE 3256 ms 192352 KiB
01_random_23.txt TLE 3284 ms 192284 KiB
01_random_24.txt TLE 3237 ms 192340 KiB
01_random_25.txt AC 725 ms 52316 KiB
01_random_26.txt AC 2250 ms 147884 KiB
01_random_27.txt AC 2680 ms 148484 KiB
01_random_28.txt AC 2915 ms 185932 KiB
01_random_29.txt AC 2894 ms 182928 KiB
01_random_30.txt AC 367 ms 39516 KiB
01_random_31.txt AC 745 ms 52908 KiB
01_random_32.txt AC 907 ms 52892 KiB
01_random_33.txt AC 1175 ms 84548 KiB
01_random_34.txt AC 1425 ms 84348 KiB
01_random_35.txt AC 1799 ms 84488 KiB
01_random_36.txt AC 2000 ms 84592 KiB
01_random_37.txt AC 2354 ms 148612 KiB
01_random_38.txt AC 2509 ms 148536 KiB
01_random_39.txt AC 2703 ms 148408 KiB
01_random_40.txt TLE 3318 ms 144148 KiB
01_random_41.txt TLE 3318 ms 145868 KiB
01_random_42.txt TLE 3319 ms 146800 KiB
01_random_43.txt TLE 3321 ms 146392 KiB
01_random_44.txt AC 1188 ms 168412 KiB
01_random_45.txt AC 1181 ms 168368 KiB
01_random_46.txt AC 1171 ms 168200 KiB
01_random_47.txt AC 1195 ms 168256 KiB
01_random_48.txt AC 80 ms 27464 KiB
01_random_49.txt AC 81 ms 27684 KiB