Submission #33926259

---

Source Code Expand

class ST
	def initialize a
		@l = (1<<(a.size-1).bit_length)-1
		@a = [nil]*@l
		@a.concat a
		@a.concat [a[-1]]*(@l+1-a.size)
		(@l-1).downto(0){|i|
			@a[i] = @a[i+i+1,2].max
		}
	end

	def max
		@a[0]
	end

	def []= i,v
		i += @l
		@a[i] = v
		@a[i] = @a[i+i+1,2].max while 0<=i = (i-1)/2
		return v
	end
end

A2D = Hash.new{|h,a| h[a] = [] }
N = gets.to_i
N.times{|d|
	gets.split.map(&:to_i).each{|a|
		A2D[a]<<d
	}
}
D = Array.new(N){[]}
Ed = ST.new [1]*N
Ea = {}
A2D.keys.sort.reverse_each{|a|
	Ea[a] = Ed.max
	A2D[a].each{|d|
		D[d]<<a
		Ed[d] = 1.0+D[d].sum{|a| Ea[a] }/6.0
	}
}

p Ed.max

Submission Info

Judge Result