07/04/2025 06:42:15

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1828. Matrix

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

As we all know, we live inside the matrix that is divided into

$N$ rows and

$N$ columns. An integer is written into each one of the NxN cells of the matrix. In order to leave the matrix, we must find the most beautiful square (square-shaped sub-matrix) contained in the matrix.

If we denote by

$A$ the sum of all integers on the main diagonal of some square, and by

$B$ the sum of the other diagonal, then the beauty of that square is

$A\ -\ B$ .

Note: The main diagonal of a square is the diagonal that runs from the top left corner to the bottom right corner.

The first line of input contains the positive integer

$N$ (

$2\ ≤\ N\ ≤\ 400$ ), the size of the matrix. The following

$N$ lines each contain

$N$ integers in the range

$[-1000,\ 1000]$ , the elements of the matrix.

The only line of output must contain the maximum beauty of a square found in the matrix.

Sample Input #1

2 
1 -2 
4 5

Sample Output #1

Sample Input #2

Sample Output #2

Sample Input #3

Sample Output #3

Source: COCI 2011/2012

25/06/2012	Лето 2012 - дорешивание (13B)
13/07/2012	Лето 2012 - 13 (B)