提出 #54698671

---

ソースコード 拡げる

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

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

(H,W,K),(Si,Sj),*A = $<.map{|ln| ln.split.map(&:to_i) }
IJKL = lambda{|i,j|
	[[i,j-1],[i,j+1],[i-1,j],[i+1,j]].select{|i,j|
		0<=i && i<H && 0<=j && j<W
	}
}
Gi,Gj = Si-1,Sj-1
Q = PQ.new
B = H.times.map{|i|
	W.times.map{|j|
		a = [A[i][j],*IJKL[i,j].map{|i,j| A[i][j] }].max
		b = a*K
		Q.enq b,[i,j,K,a]
		next b
	}
}
while (b,(i,j,k,a) = Q.deq)
	next if b<B[i][j]
	break if i==Gi && j==Gj
	next if k<1
	b,k = b-a+A[i][j],k-1
	IJKL[i,j].each{|i,j|
		Q.enq (B[i][j] = b),[i,j,k,a] if B[i][j]<b
	}
end

p B[Gi][Gj]

提出情報

ジャッジ結果