대회 링크

http://codeforces.com/contest/22

해설

A. Second Order Statistics

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

B. Bargaining Table

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

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

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

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

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

• 소스코드(hyunhwan작성)

C. System Administrator

D. Segments

E. Scheme