X-Sum Codeforces Solution | Codeforces Problem Solution 2022

X-Sum Codeforces Solution | Codeforces Problem Solution 2022

D. X-Sum

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Timur's grandfather gifted him a chessboard to practice his chess skills. This chessboard is a grid 𝑎$a$ with 𝑛$n$ rows and 𝑚$m$ columns with each cell having a non-negative integer written on it.

Timur's challenge is to place a bishop on the board such that the sum of all cells attacked by the bishop is maximal. The bishop attacks in all directions diagonally, and there is no limit to the distance which the bishop can attack. Note that the cell on which the bishop is placed is also considered attacked. Help him find the maximal sum he can get.

Solution Click Below:-  CLICK HERE

Input

The first line of the input contains a single integer 𝑡$t$ (1≤𝑡≤1000$1\le t\le 1000$) — the number of test cases. The description of test cases follows.

Lucky? Codeforces Solution

Equal Candies Codeforces Solution

Most Similar Words Codeforces Solution

X-Sum Codeforces Solution

Eating Queries Codeforces Solution

Longest Strike Codeforces Solution

White-Black Balanced Subtrees Codeforces Solution

Maximum Crossings (Easy Version) Codeforces Solution

Maximum Crossings (Hard Version) Codeforces Solution

The first line of each test case contains the integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤200$1\le n\le 200$, 1≤𝑚≤200$1\le m\le 200$).

The following 𝑛$n$ lines contain 𝑚$m$ integers each, the 𝑗$j$-th element of the 𝑖$i$-th line 𝑎𝑖𝑗$a_{ij}$ is the number written in the 𝑗$j$-th cell of the 𝑖$i$-th row (0≤𝑎𝑖𝑗≤106)$(0\le a_{ij}\le {10}^6)$

It is guaranteed that the sum of 𝑛⋅𝑚$n\cdot m$ over all test cases does not exceed 4⋅104$4\cdot {10}^4$.

Output

For each test case output a single integer, the maximum sum over all possible placements of the bishop.

Join Now for Solution:-