Submission #44067838

---

Source Code Expand

class BIT
	def initialize n
		@n = n+1 # accessing 0..n-1, 1..n internally.
		@a = [0]*@n
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end
	def lb s
		i,t,b = 0,0,1<<(@n-1).bit_length
		t += @a[i|=b] if i|b<@n && t+@a[i|b]<s while 0<b >>= 1
		return i if i<@n-1 # i は１大きい内部インデックス(もしくは 0)だけど、求めた添字が s 未満の値を返す最大の添字であり、s の lower_bound としては +1 したものを返したいから、足し引きして内部インデックスそのままの値を返す(アクセス可能な範囲(0...@n-1)なら)。
	end

	def add i,d
		i += 1
		while i<@n
			@a[i] += d
			i += i&-i
		end
	end
	def inc i; add i,1 end
	def dec i; add i,-1 end
end

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

T = [],[],[]
TX.each{|t,x|
	T[t]<<x
}
T.each(&:sort!)

X = 0,*TX.map{_2}.uniq.sort.reverse
I = X.each_with_index.to_h
Ord = BIT.new I.size+1
Sum = BIT.new I.size+1

T[0].each{|x|
	i = I[x]
	Ord.inc i
	Sum.add i,x
}

p [0,*T[2].reverse].map.with_index{|co,dm|
	co.times{
		x = T[1].pop
		break if ! x
		i = I[x]
		Ord.inc i
		Sum.add i,x
	}
	m = M-dm
	next 0 if m<1
	i = Ord.lb m
	next Sum[I.size] if ! i
	next 0 if i<1
	m -= Ord[i-1]
	next Sum[i-1]+m*X[i]
}.max

Submission Info

Judge Result