대회 링크

http://codeforces.com/contest/22

해설

A. Second Order Statistics

간단한 정렬 문제이므로 생략

B. Bargaining Table

$ O( N^{2} M^{2} ) $ 해법

• 모든 $(i,j)$에 대해 top-left가 $(0,0)$이고 bottom-right가 $(i,j)$인 사각형 구간의 누적합(1의 개수)를 미리 계산한 테이블을 가지고 있으면 임의의 top-left가 $(a,b)$, bottom-right가 $(c,d)$인 구간의 1의 개수를 $O(1)$에 구할 수 있다.
• 이를 이용하여 모든 구간이 0인 구간 중 최대가 되는 사각형 구간이 답이 된다. 이 때 둘레는 $(height+width) * 2 $로 계산 가능하다.

$ O( N^{3} M^{2} )$ 해법

• 우선 문제 조건이 $25^5$기 때문에 가능한 해법
• 각 행에 대한 누적합을 구하고 지정한 사각형 구간에 대해 $O(N)$으로 스캔하여 0만 존재하는 구간인지 확인하여 후보 구간을 선별한다.

• 선별된 구간 중 둘레가 최대가 되는 구간이 답이 된다.

• 소스코드(hyunhwan작성)

C. System Administrator

D. Segments

E. Scheme