Submission #27502421

---

Source Code Expand

class BIT
	def initialize n
		@a = [0]*(n+1)
	end

	def [] i
		i += 1
		v = 0
		while 0<i
			v += @a[i]
			i &= i-1
		end
		return v
	end

	def inc i
		i += 1
		while i<@a.size
			@a[i] += 1
			i += i&-i
		end
	end
end

N,*H = $<.read.split.map(&:to_i)

I = [0]*(N+1)
V = [0]*(N+1)
B = BIT.new N+1
H.each_with_index{|h,i|
	I[h] = i
	V[h] = i-B[h]
	B.inc h
}

D = [0]*(N+1)
1.upto(N){|h|
	d,v = 0,BIT.new(N+1)
	D[h] = h.downto(1).map.with_index{|h,i|
		d += V[h]+i-2*v[I[h]]
		v.inc I[h]
		next D[h-1]+d
	}.min
}

p D[N]

Submission Info

Judge Result