Submission #27772767

---

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,J0s = [I1,J0].map{|is| is.values_at(*As).uniq.sort }

max = 0
while i0 = I0s.shift
	i1s = I1s.group_by{|i1| i1<i0 ? 0 : [S/(i1-i0+1),W].min }
	i1s.delete 0
	i1s = i1s.values.map(&:pop).sort
	while i1 = i1s.shift and 0<w = S/(i1-i0+1)
		ain,j1s = {},J1s.dup
		while j1 = j1s.shift
			next if 1>Aj1[j1].count{|a|
				ain[a] = 1 if I1[a]<=i1
			} or ain.size<=max
			ain.reject!{|a,|
				w<=j1-J0[a]
			}
			max = ain.size if max<ain.size
		end
	end
	Ai0[i0].each{|a|
		Aj1[J1[a]].shift
	}
end

p Z-max

Submission Info

Judge Result