Submission #40683415

---

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 [] l,r=l
		return if r<l
		l,r = @l+l,@l+r
		lx,rx = @a[l],@a[r]
		lx,rx,l,r = [@a[l],lx].max,[@a[r],rx].max,l/2,r/2-1 until r<l
		return [lx,rx].max
	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

(N,),*RCX = $<.map{|ln| ln.split.map(&:to_i) }
R = RCX.group_by{|r,|r}.transform_values{|rcx| rcx.sum{_3} }.tap{|h| h.default = 0 }
C = RCX.group_by{_2}.transform_values{|rcx| rcx.sum{_3} }.tap{|h| h.default = 0 }
X = RCX.group_by(&:shift).tap{|h| h.default = [] }
Cs = C.keys.sort
IC = Cs.each_with_index.to_h

CX = ST.new C.values_at(*Cs)
p [0,*R.keys.sort].each_cons(2).map{|r0,r|
	X[r0].each{|c,x|
		CX[IC[c]] += x
	}
	X[r].each{|c,x|
		CX[IC[c]] -= x
	}
	next R[r]+CX.max
}.max

Submission Info

Judge Result