Submission #58342271

---

Source Code Expand

class PQ
	def initialize
		@h = [] # max-heap
	end

	def enq d
		@h << d
		up_heap
	end
	def deq
		return unless @h[0]
		@h[0],@h[-1] = @h[-1],@h[0]
		d = @h.pop
		dn_heap if @h[0]
		return d
	end
 
private
	def up_heap
		d = @h[i=@h.size-1]
		while 0<i
			iP = (i-1)/2
			break if d<=@h[iP]
			@h[i],i = @h[iP],iP
		end
		@h[i] = d
	end
	def dn_heap
		d = @h[i=0]
		z = @h.size
		until z <= iC = i+i+1
			iC += 1 if iC+1<z && @h[iC]<@h[iC+1]
			break if @h[iC]<=d
			@h[i],i = @h[iC],iC
		end
		@h[i] = d
	end
end

(N,W),*WV = $<.map{|ln| ln.split.map(&:to_i) }

W2V = [0]*(W+1)
WV.group_by(&:shift).each{|dw,vs|
	kx = W/dw
	dvs = PQ.new
	vs.each{|v,|
		(0..kx).map{|k| k*v-k*k }.each_cons(2){|v0,v1|
			dvs.enq v1-v0
		}
	}
	dvs = kx.times.map{ dvs.deq }
	W.downto(0){|w|
		v = W2V[w]
		dv = dvs.dup
		(w+dw).step(W,dw){|w|
			v += dv.shift
			W2V[w] = v if W2V[w]<v
		}
	}
}

p W2V.max

Submission Info

Judge Result