提出 #57009717

ソースコード 拡げる

N,M,K = gets.split.map(&:to_i)
E = Array.new(N){[]}
M.times{
	a,b,d = gets.split.map(&:to_i)
	a,b = a-1,b-1
	E[a]<<[b,d]
	E[b]<<[a,d]
}
D = N.times.map{|s|
	ds = [10**13]*N
	ds[s] = 0
	*q = s
	while a = q.shift
		d0 = ds[a]
		E[a].each{|b,d|
			d += d0
			if d<ds[b]
				ds[b] = d
				q<<b
			end
		}
	end
	next ds
}
Ev = [0,0,0],*K.times.map{ gets.split.map(&:to_i).then{|c,t| [c-1,t] } }.sort_by{_2}
1.upto(K){|i|
	c,t = Ev[i]
	ds = D[c]
	a = Ev[0,i].filter_map{|c0,t0,a0|
		a0+1 if t0+ds[c0]<=t
	}.max
	if a
		Ev[i]<<a
	else
		Ev[i]<<0
		Ev[i][1] = 10**13
	end
}
p Ev.map{_3}.max

提出情報

提出日時
問題 D - Attend Many Events
ユーザ ds14050
言語 Ruby (ruby 3.2.2)
得点 450
コード長 622 Byte
結果 AC
実行時間 274 ms
メモリ 40628 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 450 / 450
結果
AC × 3
AC × 33
セット名 テストケース
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, 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, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt, 02_handmade_09.txt, 02_handmade_10.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 128 ms 17132 KiB
00_sample_02.txt AC 42 ms 16808 KiB
00_sample_03.txt AC 43 ms 17548 KiB
01_random_01.txt AC 93 ms 19124 KiB
01_random_02.txt AC 271 ms 29808 KiB
01_random_03.txt AC 100 ms 22684 KiB
01_random_04.txt AC 223 ms 26660 KiB
01_random_05.txt AC 149 ms 22932 KiB
01_random_06.txt AC 251 ms 32256 KiB
01_random_07.txt AC 81 ms 25220 KiB
01_random_08.txt AC 241 ms 29228 KiB
01_random_09.txt AC 231 ms 26296 KiB
01_random_10.txt AC 252 ms 27128 KiB
01_random_11.txt AC 147 ms 21996 KiB
01_random_12.txt AC 250 ms 30524 KiB
01_random_13.txt AC 113 ms 18860 KiB
01_random_14.txt AC 239 ms 26864 KiB
01_random_15.txt AC 156 ms 25808 KiB
01_random_16.txt AC 264 ms 27244 KiB
01_random_17.txt AC 87 ms 25236 KiB
01_random_18.txt AC 274 ms 29704 KiB
01_random_19.txt AC 127 ms 20700 KiB
01_random_20.txt AC 250 ms 32316 KiB
02_handmade_01.txt AC 231 ms 25604 KiB
02_handmade_02.txt AC 215 ms 25400 KiB
02_handmade_03.txt AC 230 ms 40628 KiB
02_handmade_04.txt AC 91 ms 25212 KiB
02_handmade_05.txt AC 51 ms 23580 KiB
02_handmade_06.txt AC 132 ms 20048 KiB
02_handmade_07.txt AC 91 ms 18184 KiB
02_handmade_08.txt AC 222 ms 28008 KiB
02_handmade_09.txt AC 164 ms 29332 KiB
02_handmade_10.txt AC 164 ms 29368 KiB