Submission #45760450

Source Code Expand

(N,H),X,*PF = $<.map{|ln| ln.split.map(&:to_i) }
H1 = H+1
Inf = 10**9
D = Array.new(H1){ [Inf]*H1 }

x0 = 0
ds0 = D.map(&:dup)
ds0[0][H] = 0
PF.zip(X){|(p,f),x|
	ds1 = D.map(&:dup)
	dx = x-x0
	dx.upto(H){|a0|
		ds0a = ds0[a0-dx]
		dx.upto(H){|b|
			d0 = ds0a[b]
			next if d0==Inf

			b0 = b-dx
			d1 = d0+p
			a1 = a0-f
			a1 = 0 if a1<0
			b1 = b0+f
			b1 = H if H<b1
			ds1a0 = ds1[a0]
			ds1a1 = ds1[a1]

			ds1a0[b1] = d1 if d1<ds1a0[b1] # 往路で給油する
			ds1a1[b0] = d1 if d1<ds1a1[b0] # 復路で給油する
			ds1a0[b0] = d0 if d0<ds1a0[b0] # 給油しない
		}
	}
	x0 = x
	ds0 = ds1
}
dx = 2*(X[-1]-x0)
M = (dx..H).map{|a|
	ds0[a-dx][a..].min
}.min||Inf

p(M==Inf ? -1 : M)

Submission Info

Submission Time
Task F - Fuel Round Trip
User ds14050
Language Ruby (ruby 3.2.2)
Score 550
Code Size 734 Byte
Status AC
Exec Time 1970 ms
Memory 46444 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 550 / 550
Status
AC × 3
AC × 37
Set Name Test Cases
Sample sample00.txt, sample01.txt, sample02.txt
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt
Case Name Status Exec Time Memory
sample00.txt AC 44 ms 17600 KiB
sample01.txt AC 43 ms 17152 KiB
sample02.txt AC 44 ms 17412 KiB
testcase00.txt AC 43 ms 18212 KiB
testcase01.txt AC 50 ms 18216 KiB
testcase02.txt AC 274 ms 18504 KiB
testcase03.txt AC 270 ms 18532 KiB
testcase04.txt AC 550 ms 32300 KiB
testcase05.txt AC 1547 ms 42728 KiB
testcase06.txt AC 1820 ms 46444 KiB
testcase07.txt AC 1943 ms 46216 KiB
testcase08.txt AC 833 ms 20196 KiB
testcase09.txt AC 80 ms 20212 KiB
testcase10.txt AC 1383 ms 41932 KiB
testcase11.txt AC 1864 ms 46308 KiB
testcase12.txt AC 1681 ms 46112 KiB
testcase13.txt AC 786 ms 19496 KiB
testcase14.txt AC 1353 ms 44580 KiB
testcase15.txt AC 1249 ms 41484 KiB
testcase16.txt AC 1530 ms 45792 KiB
testcase17.txt AC 1609 ms 46124 KiB
testcase18.txt AC 706 ms 19016 KiB
testcase19.txt AC 75 ms 20852 KiB
testcase20.txt AC 694 ms 42404 KiB
testcase21.txt AC 729 ms 38684 KiB
testcase22.txt AC 696 ms 41888 KiB
testcase23.txt AC 641 ms 19184 KiB
testcase24.txt AC 926 ms 40928 KiB
testcase25.txt AC 395 ms 29184 KiB
testcase26.txt AC 1835 ms 46180 KiB
testcase27.txt AC 1970 ms 46260 KiB
testcase28.txt AC 771 ms 20524 KiB
testcase29.txt AC 1589 ms 45872 KiB
testcase30.txt AC 661 ms 36460 KiB
testcase31.txt AC 1320 ms 45036 KiB
testcase32.txt AC 1498 ms 45440 KiB
testcase33.txt AC 754 ms 19520 KiB