Dilhan's Computing Contest 1 P3 - Soccer Court

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 5.0s
Memory limit: 1G

Author:
Problem type

You have been tasked by your city council with creating a soccer court in your local park. You go over to the park to investigate.

The park consists of a rectangle-shaped region consisting of a N \times M grid of grass squares. Each square has a grass speed of s_{i,j} representing how fast the ball will roll through that cell.

A valid court consists of an axis-aligned subrectangle of the park with integer height and even width. This court will be split into equally-sized halves by a vertical line to create an offensive zone and a defensive zone for each team. To allow for construction of spectator seating, the court cannot be rotated and the midline must be vertical. The court must also satisfy one additional constraint - to ensure each team has an equal offensive advantage, the sum of the grass speeds in each of the two halves must be the same.

Of course there may be more than one possible valid court within the park. To maximize player capacity, you will choose a court with maximum area.

Given this information, calculate the size of the court that you will pick out. If there is no valid court, output 0 instead.

Constraints

1 \leq N \leq 800

1 \leq M \leq 400

1 \leq s_{i,j} \leq 10^9

Input Specification

The first line contains two integers N and M: the height and width of the park respectively.

The next N lines contain M integers each, representing the grass speed s_{i,j}.

Output Specification

Output a single integer - the maximum possible area of a valid court.

If no valid court exists, output 0.

Sample Input 1

4 6
1 2 3 4 5 6
2 3 4 5 6 7
9 9 7 5 1 1
8 8 7 7 6 6

Sample Output 1

18

Sample Input 2

7 5
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10
10 10 11 10 10
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10

Sample Output 2

14

Comments

There are no comments at the moment.