Ratar
레이팅 미적용의견: 0
\(1^{st}\) round, September \(28^{th}\), 2013
After Mirko's failed stint as a coach and a passing obsession with Croatian meat delicacies, his weight
problems have motivated him to work hard as a farmer. He has moved to a village where his friend
Slavko lives. Farmers in the village share a large common plot of land in the shape of a \(N \times N\) square,
divided into N2 unit squares. A unit square at coordinates^{2} (i, j) brings in the income of A_{ij}, which can
be negative (for example, if the square has to be maintained but is not cultivated). The farmers always
divide the common land into smaller rectangular fields with edges parallel to the common land
edges.
Slavko is skeptical of Mirko since his failure as a coach, so he insists that both of them are assigned
land with the same total income, but also thet the two plots share exactly one common corner so
that the two friends can keep an eye on each other (Slavko knows that Mirko is prone to mischief). The
common corner must be the only point where the two plots meet, in order to prevent bord\(er-re\)lated
arguments.
You are given a description of the common land plot. Find the total number of plot pairs that satisfy
Slavko's criteria.
In test data worth at least 40% of total points, N will be at most 10.
The first line of input contains the positive integer N (\(1 \le N \le 50\)), the dimensions of the common
land plot.
Each of the following N lines contains N spa\(ce-se\)parated numbers A_{ij}(-\(1000 < A_{ij}< 1000\)), the income
provided by the respective cell.
The first and only line of output must contain the totl number of plot pairs satisfying the given
condition.
3
1 2 3
2 3 4
3 4 874
-1 -1 -1 -1
1 2 3 4
1 2 3 4
1 2 3 4105
-1 -1 -1 -1 -1
-2 -2 -2 -2 -2
-3 -3 -3 -3 -3
-4 -4 -4 -4 -4
-5 -5 -5 -5 -536Clarification of the first example: The possible rectangle pairs are:
(0,0)-(1,1) and (2,2)-(2,2), (1,0)-(1,0) and (0,1)-(0,1), (2,0)-(2,0) and (1,1)-(1,1), (1,1)-(1,1) and (0,2)-(0,2),
(2,1)-(2,1) and (1,2)-(1,2), (2,0)-(2,1) and (0,2)-(1,2), (1,0)-(2,0) and (0,1)-(0,2).
2
The first number in the parenthesis denotes the row, and the second number denotes the column
평가 및 의견
Ratar
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ratar