codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1676D.md (1734B)


      1 Source: https://codeforces.com/problemset/problem/1676/D
      2 
      3 D. X-Sum
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 Input
     26 
     27 The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.
     28 
     29 The first line of each test case contains the integers $n$ and $m$ ($1 \le n \le 200$, $1 \leq m \leq 200$).
     30 
     31 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\leq a_{ij} \leq 10^6)$
     32 
     33 It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $4\cdot10^4$.
     34 
     35 Output
     36 
     37 For each test case output a single integer, the maximum sum over all possible placements of the bishop.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 4 4
     47 
     48 1 2 2 1
     49 
     50 2 4 2 4
     51 
     52 2 2 3 1
     53 
     54 2 4 2 4
     55 
     56 2 1
     57 
     58 1
     59 
     60 0
     61 
     62 3 3
     63 
     64 1 1 1
     65 
     66 1 1 1
     67 
     68 1 1 1
     69 
     70 3 3
     71 
     72 0 1 1
     73 
     74 1 0 1
     75 
     76 1 1 0
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 20
     83 1
     84 5
     85 3
     86 ```
     87 
     88 Note
     89 
     90 For the first test case here the best sum is achieved by the bishop being in this position:
     91 
     92  ![](https://espresso.codeforces.com/0a1581e369415190ead57aa7162be7962b22dbed.png)