Submission #32032452

Source Code Expand

P,N,M,K = 998244353,*gets.split.map(&:to_i)
if K<1
	p M.pow(N,P)
	exit
end

d0 = [1]*(M+1)
d0[0] = 0
(N-1).times{
	d1 = [0]*(M+1)
	sk = d0[K..M].sum%P
	(1..M).each{|j|
		sk += d0[j-K] if 0<j-K
		sk -= d0[j+K-1] if j+K-1<=M
		d1[j] = sk
	}
	d0 = d1
}

p d0[1,M].sum%P

Submission Info

Submission Time
Task E - Distance Sequence
User ds14050
Language Ruby (2.7.1)
Score 0
Code Size 287 Byte
Status TLE
Exec Time 2208 ms
Memory 59892 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 14
TLE × 6
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.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, 02_max_01.txt, 02_max_02.txt, 02_max_03.txt, 02_max_04.txt, 02_max_05.txt, 02_max_06.txt, 02_max_07.txt, 02_max_08.txt, 02_max_09.txt, 02_max_10.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 64 ms 14236 KiB
00_sample_02.txt AC 64 ms 14268 KiB
00_sample_03.txt AC 96 ms 16004 KiB
01_random_01.txt AC 67 ms 14584 KiB
01_random_02.txt TLE 2207 ms 37564 KiB
01_random_03.txt AC 113 ms 16416 KiB
01_random_04.txt AC 199 ms 19356 KiB
01_random_05.txt TLE 2207 ms 44024 KiB
01_random_06.txt AC 269 ms 22768 KiB
01_random_07.txt AC 620 ms 37188 KiB
02_max_01.txt TLE 2208 ms 59892 KiB
02_max_02.txt TLE 2206 ms 26876 KiB
02_max_03.txt AC 1613 ms 45920 KiB
02_max_04.txt AC 418 ms 49856 KiB
02_max_05.txt AC 63 ms 14368 KiB
02_max_06.txt AC 611 ms 47980 KiB
02_max_07.txt AC 58 ms 14196 KiB
02_max_08.txt AC 64 ms 14276 KiB
02_max_09.txt TLE 2207 ms 38456 KiB
02_max_10.txt TLE 2207 ms 46240 KiB