An agronomy drone has surveyed a rectangular field laid out as a grid with m rows and n columns; the reading at row r, column c is fertility[r][c]. The drone's soil probe samples a fixed bowtie-shaped cluster of 7 plots at a time: given a top-left corner at row i, column j (spanning the 3 consecutive rows i, i+1, i+2 and the 3 consecutive columns j, j+1, j+2), the probe reads all three cells of the top row, only the single centre cell of the middle row, and all three cells of the bottom row — the two outer cells of the middle row are skipped. Marking a sampled cell X and a skipped cell . , the pattern looks like:
X X X
. X .
X X X
The probe can be placed at any (i, j) with 0 <= i <= m-3 and 0 <= j <= n-3, so its whole bowtie fits inside the field. Find the placement that maximizes the sum of the 7 sampled fertility readings.
The first line contains two integers m and n. Each of the next m lines contains n integers, the values fertility[r][0], ..., fertility[r][n-1] for that row.
Print a single integer: the maximum possible sum of fertility readings over any valid bowtie placement.
Example 1
Input
3 4 1 2 3 4 0 5 0 0 4 3 2 1
Expected
20
Explanation
Two placements fit (row fixed at 0 since m=3): at column 0 the sum is (1+2+3) + 5 + (4+3+2) = 20; at column 1 it is (2+3+4) + 0 + (3+2+1) = 15. The best is 20.
Example 2
Input
4 3 5 5 5 1 9 1 2 2 2 8 1 1
Expected
30
Explanation
Two placements fit (column fixed at 0 since n=3): at row 0 the sum is (5+5+5) + 9 + (2+2+2) = 30; at row 1 it is (1+9+1) + 2 + (8+1+1) = 23. The best is 30.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →