Submission #27797091

---

Source Code Expand

(H,W,S),*A = $<.map{|ln| ln.split.map(&:to_i) }

I0,I1,J0,J1 = 4.times.map{ [nil]*257 }
A.each_with_index{|r,i|
	r.each_with_index{|a,j|
		I0[a] ||= i
		I1[a] = i
		J0[a] = j unless J0[a]&.<j
		J1[a] = j unless J1[a]&.>j
	}
}
Z = I0.compact.size
As = 257.times.select{|a|
	I0[a] && (I1[a]-I0[a]+1)*(J1[a]-J0[a]+1)<=S
}.sort_by{|a| I0[a] }
Ai0,Aj1 = [I0,J1].map{|is| As.group_by{|a| is[a] } }
I0s,J1s = [Ai0,Aj1].map{|ai| ai.keys.sort }
I1s = I1.values_at(*As).uniq.sort

max = 0
while i0 = I0s.shift
	I1s.shift while I1s[0]<i0
	i1s = I1s.chunk{|i1| [S&1|S/(i1-i0+1),W].min }.map{|_,as| as[-1] }
	while i1 = i1s.shift
 		w,ain,j1s = S/(i1-i0+1),[],J1s.dup
		while j1 = j1s.shift
			next if 1>Aj1[j1].count{|a|
				ain << w+J0[a] if I1[a]<=i1
			} or ain.size<=max
			ain.reject!{|wj0| wj0<=j1 }
			max = ain.size if max<ain.size
		end
	end
	Ai0[i0].each{|a|
		Aj1[J1[a]].shift
		J1s.delete_at J1s.bsearch_index{|j1| J1[a]<=j1 } if Aj1[J1[a]].empty?
	}
end

p Z-max

Submission Info

Judge Result