Submission #30174747

---

Source Code Expand

class Span
	def initialize t,v
		@t,@v = t,v
		@l,@left = 0
		@r,@right = 0
	end

	def travel
		travel_s + (@left ? @left.travel_l : 0) + (@right ? @right.travel_r : 0)
	end
	def travel_s
		lo,hi = @l,@r
		lo,hi = hi,lo if hi<lo
		x = [@v,hi+(@t+lo-hi)/2.0].min
		t = @t-(x-hi)-(x-lo)
		return 0.5*(x*t*2+(x-lo)*(x+lo)+(x-hi)*(x+hi))
	end
	def travel_l
		travel_s + (@left ? @left.travel_l : 0)
	end
	def travel_r
		travel_s + (@right ? @right.travel_r : 0)
	end

	def << right
		if @right != right
			@right = right
			accl_r right.accl_l [@v,@l+@t].min
			right >> self
		end
		return right
	end
	def >> left
		if @left != left
			@left = left
			accl_l left.accl_r [@v,@r+@t].min
			left << self
		end
		return left
	end
	def accl_l x
		accl_r @right.accl_l [@v,@l+@t].min if @right if @l != @l = [x,@v,@r+@t].min
		return @l
	end
	def accl_r x
		accl_l @left.accl_r [@v,@r+@t].min if @left if @r != @r = [x,@v,@l+@t].min
		return @r
	end
end

N = gets.to_i
T = $<.map{|ln| ln.split.map(&:to_i) }.transpose.map{|t,v| Span.new t,v }.inject:<<
p T.travel

Submission Info

Judge Result