Gargari and Bishops

Codeforces

Medium

Arrays

Matrices

Math

Gargari and Bishops

Find two bishops on an $n \times n$ board, one on a black square and one on a white square, such that the sum of values on both bishops' diagonals is maximized.

Acceptance 0%

Start Practice

Problem Statement

You are given an $n \times n$ table of integers. Consider placing a bishop on any cell of the board.

A bishop attacks every cell on the two diagonals passing through its position. For a bishop placed at cell $(i, j)$ , define its score as the sum of all values on both diagonals that pass through $(i, j)$ , counting the cell itself only once.

Choose two cells:

one on a black square,
one on a white square,

so that the sum of their scores is as large as possible.

Return the maximum possible total score and the coordinates of the two chosen cells.

The standard chessboard coloring is used: a cell $(i, j)$ is black if $(i + j)$ is even, otherwise white.

Input Format

Input

The first line contains an integer $n$ .
Each of the next $n$ lines contains $n$ integers describing the board.

Output

Print the maximum total score, followed by the coordinates of the chosen black cell and white cell.

If multiple answers exist, any valid one may be returned.

Output Format

Output

Print four integers for the best black cell and four integers for the best white cell, or otherwise the maximal total value and coordinates in the required order depending on the implementation format used by the platform.

For practice purposes, the key goal is to compute:

the best black-square bishop position,
the best white-square bishop position,
the sum of their diagonal scores.

Constraints

$1 \le n$
The board contains integer values.
A correct solution should run in $O(n^2)$ or similar time.

Examples

Sample cases returned by the problem API.

Example 1

Input

2
1 2
3 4

Output

8
1 2
2 1

Explanation

Cell $(1,2)$ has diagonal sum $2+3=5$ and cell $(2,1)$ has diagonal sum $3+2=5$ if diagonals are counted over the board; since each cell belongs to one black and one white square, the best valid pair is one black and one white cell. This tiny example illustrates the idea of evaluating both colors separately.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress