시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1110 | 509 | 371 | 46.433% |
상근이와 선영이는 도심 속의 삶에 싫증을 느꼈고, 친구 현수가 있는 시골로 농사를 지으려 내려왔다. 현수의 땅은 크기가 N×N 인 정사각형이고, 땅은 단위 정사각형 1×1로 나누어져 있다. 각 단위 정사각형 (i,j)의 수익은 Aij이다. Aij는 음수가 될 수도 있다. (땅을 경작하지 않아 관리가 필요한 경우)
현수는 자신의 땅의 일부를 상근이와 선영이에게 빌려주려고 한다. 두 사람이 받게되는 땅은 항상 직사각형 모양이고, 변은 축에 평행하다.
현수는 두 사람이 농사지을 땅의 수익의 합이 같게 되도록 땅을 빌려주려고 한다. 또, 경쟁심을 유도하기위해 두 땅은 꼭짓점 하나에서만 만나게 하려고 한다. (변을 공유할 수는 없다)
현수 땅의 정보가 주어졌을 때, 땅을 나누어주는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 땅의 크기 N (1 ≤ N ≤ 50)이 주어진다.
다음 N개의 줄의 N번째 숫자 Aij는 부분 정사각형 (i,j)의 수익이다. (-1000 < Aij < 1000)
현수의 조건을 만족시키면서 땅을 빌려주는 방법의 수를 출력한다.
3 1 2 3 2 3 4 3 4 8
7
4 -1 -1 -1 -1 1 2 3 4 1 2 3 4 1 2 3 4
10
5 -1 -1 -1 -1 -1 -2 -2 -2 -2 -2 -3 -3 -3 -3 -3 -4 -4 -4 -4 -4 -5 -5 -5 -5 -5
36
가능한 방법은 다음과 같다.
Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #1 3번