提出 #16543158

---

ソースコード 拡げる

class ST
	def initialize n,iv
		@l = (1<<(n-1).bit_length)-1
		@h = [iv]*(@l+@l+1)
	end

	def max
		return @h[0]
	end

	def [] l,r
		return if r < l
		l,r = @l+l+1,@l+r+1
		lx,rx = @h[l-1],@h[r-1]
		while l <= r
			lx = @h[l-1] if lx < @h[l-1]
			rx = @h[r-1] if rx < @h[r-1]
			l = (l+1)/2
			r = (r-1)/2
		end
		return lx < rx ? rx : lx
	end

	def []= i,v
		j = @l+i+1
		@h[j-1] = v
		@h[j-1] = v while 0 < (j/=2) && @h[j-1] < v
		return v
	end
end

(R,C,K),*RCV = $<.map{|ln| ln.split.map(&:to_i) }

Rs = Array.new(R){ [] }
RCV.each{|s,d,v|
	Rs[s-1] << [d-1,v]
}

r0 = ST.new C,0
while r = Rs.shift
	r.empty? and next or r.sort!

	c0,vs = 0,[0]*4
	until r.empty?
		c,v = r.shift
		r0c = r0[c0,c]
		vs[0] = r0c if vs[0] < r0c
		vs[3] = vs[2]+v if vs[3] < vs[2]+v
		vs[2] = vs[1]+v if vs[2] < vs[1]+v
		vs[1] = vs[0]+v if vs[1] < vs[0]+v
		r0[c] = vs.max
		c0 = c+1
	end
end

p r0.max

提出情報

ジャッジ結果