Дана прямоугольная целочисленная таблица. Найти четыре ячейки, образующие прямоугольник с максимальной суммой значений

[Simon1712]

Дана прямоугольная таблица, состоящая из m строк и n столбцов. На пересечении i-й строки и j-го столбца записано целое число aij.

Требуется найти такие четыре различные ячейки таблицы, чтобы их центры были вершинами прямоугольника со сторонами, параллельными сторонам таблицы, а сумма чисел, записанных в этих ячейках, была максимальна.

Формат входных данных
На первой строке записаны два натуральных числа m и n (2 ≤ m, n ≤ 500). Далее следует описание таблицы – m строк, каждая из которых содержит по n целых чисел (-107 ≤ aij ≤ 107).

Формат выходных данных
На первой строке выходного файла выведите целое число r – максимальную сумму выбранных элементов, на второй строке выведите 4 натуральных числа x1, y1, x2, y2 – координаты левой верхней и правой нижней из выбранных ячеек, соответственно (1 ≤ x1 < x2 ≤ m, 1 ≤ y1 < y2 ≤ n). Если оптимальных решений несколько, выведите любое.


Пример
Входные данные

5 5
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 3 1
1 1 1 1 1

Выходные данных

7
2 2 4 4


Помогите решить! НА ум приходит только перебор, но он не зайдет по времени, код можно не писать - главное подать идею решения

[cyberdev]

А для чего задачка? Если не секрет.

[Serge_Bliznykov]

Сообщение от cyberdev

А для чего задачка? Если не секрет.

странный Вы...
Ну для чего решают олимпиадные задачи?
В данном случае, скорее всего для того, чтобы получить оценку или зачёт.
А ещё возмножно (хоть и ОЧЕНЬ маловероятно) что TC решает задачу "для себя", чтобы поднять свой программерский скил!

А по сути самой задачи.
я другого варианта решения, кроме перебора, и не вижу.

[Poma][a]

ИМХО, тут простой перебор.. При таких ограничениях - он будет просто летать..
Просто поставить в левый верхний угол матрицу 2 на 2, посщитать её сумму, запомнить координаты, перенести матрицу на 1 позицию влево, снова найти сумму, если она превышает предыдущую, заменить сумму, заменить координаты.. Когда дошли до конца строки, сдвинуть левый верхний угол "маленькой" матрицы, в позицию (2,1) и снова..

[cyberdev]

странный Вы...
Ну для чего решают олимпиадные задачи?
В данном случае, скорее всего для того, чтобы получить оценку или зачёт.
А ещё возмножно (хоть и ОЧЕНЬ маловероятно) что TC решает задачу "для себя", чтобы поднять свой программерский скил!

Ну и что здесь странного?
Программист решает задачи ради какого-то результата. К стати, автор так и не ответил.

[Kix.IV]

Возможно, если расположить все числа по убыванию, а потом перебором найти максимальные четыре, координаты которых сооставляют прямоугольник, то выйдет немного быстрее чем простой перебор. Но выйгрышь по времени если будет, то будет небольшой и не во всех случаях.

Вот несколько найденных в сети решений:

program problem;

uses
	math, sysutils;

const
	maxn = 500;

var
	i, j, m, n: longint;
	a: array [1..maxn, 1..maxn] of longint;
	k, l1, l2, max1, max2, best: longint;
	x1, y1, x2, y2: longint;

begin
	reset(input, 'problem.in');
	rewrite(output, 'problem.out');

	readln(m, n);
	assert((2 <= m) and (m <= 500) and (2 <= n) and (n <= 500));
	for i := 1 to m do begin
		for j := 1 to n do begin
			read(a[i][j]);
			assert(abs(a[i][j]) <= 10000000);
		end;
		readln;
	end;

	best := -maxlongint;
	for i := 1 to m do begin
		for j := i + 1 to m do begin
			max1 := -maxlongint;
			max2 := -maxlongint;
			for k := 1 to n do begin
				if a[i][k] + a[j][k] > max1 then begin
					l2 := l1;
					max2 := max1;
					l1 := k;
					max1 := a[i][k] + a[j][k];
				end else if	a[i][k] + a[j][k] > max2 then begin
					l2 := k;
					max2 := a[i][k] + a[j][k];
				end;
			end;
			if max1 + max2 > best then begin
				best := max1 + max2;
				x1 := i;
				y1 := min(l1, l2);
				x2 := j;
				y2 := max(l1, l2);
			end;
		end;
	end;

	writeln(best);
	writeln(x1, ' ', y1, ' ', x2, ' ', y2);

	close(input);
	close(output);
end.

{$r-,q-,o+}
{$apptype console}
type
  int = longint;

const
  program_name = 'problem';
  inf = 1000000000;

var
  a: array [1..500, 1..500] of int;
  m1, m2: array [1..500] of int;
  n, m: int;
  u1, u2, i, j, d: int;
  max1, max2, max1i, max2i: int;
  maxi1, maxi2, maxj1, maxj2: int;
  max: int;

begin
  reset(input, program_name + '.in');
  rewrite(output, program_name + '.out');

  read(n, m);
  for i:=1 to n do
    for j:=1 to m do begin
            read(a[i][j]);
            assert(abs(a[i][j]) <= 10000000);
        end;


  for i:=1 to n do
  begin
    m1[i]:=-inf;
    m2[i]:=-inf;
    for j:=1 to m do
    begin
      if (a[i][j] > m1[i]) then
      begin
        m2[i]:=m1[i];
        m1[i]:=a[i][j];
        continue;
      end;

      if (a[i][j] > m2[i]) then
      begin
        m2[i]:=a[i][j];
        continue;
      end;
    end;
  end;

  max:=-inf;
  maxi1:=-1;
  maxi2:=-1;
  maxj1:=-1;
  maxj2:=-1;
  for u1:=1 to n do
    for u2:=u1 + 1 to n do
    begin
      max1:=-inf;
      max2:=-inf;
      max1i:=-1;
      max2i:=-1;
      if (m1[u1] + m2[u1] + m1[u2] + m2[u2] <= max) then
        continue;

      for i:=1 to m do
      begin
        d:=a[u1][i] + a[u2][i];
        if (d > max1) then
        begin
          max2:=max1;
          max2i:=max1i;

          max1:=d;
          max1i:=i;
          continue;
        end;

        if (d > max2) then
        begin
          max2:=d;
          max2i:=i;
          continue;
        end;
      end;

      if (max1 + max2 > max) then
      begin
        max:=max1 + max2;
        maxi1:=u1;
        maxi2:=u2;
        maxj1:=max1i;
        maxj2:=max2i;
      end;
    end;

  writeln(max);
  if (maxj1 < maxj2) then
    writeln(maxi1, ' ', maxj1, ' ', maxi2, ' ', maxj2)
  else
    writeln(maxi1, ' ', maxj2, ' ', maxi2, ' ', maxj1);
end.

{$o+,q-,r-}
{$APPTYPE console}

uses
    Math, SysUtils;

const
    maxn = 500;
    filename = 'problem';
    inf = $77777777;

type
    int = longint;

var
    n, m, i, j, r, k, k1, k2: int;
    a: array[1 .. maxn, 1 .. maxn] of int;

begin
    reset(input, filename + '.in');
    rewrite(output, filename + '.out');

    read(n, m);
    for i := 1 to n do
        for j := 1 to m do begin
            read(a[i][j]);
            assert(abs(a[i][j]) <= 10000000);
        end;

    r := -inf;
    for i := 1 to n do
        for j := i + 1 to n do begin
            if (a[i][1] + a[j][1] > a[i][2] + a[j][2]) then begin
                k1 := a[i][1] + a[j][1];
                k2 := a[i][2] + a[j][2];
            end
            else begin
                k2 := a[i][1] + a[j][1];
                k1 := a[i][2] + a[j][2];
            end;
            for k := 3 to m do begin
                if (a[i][k] + a[j][k] > k1) then
                    k1 := a[i][k] + a[j][k]
                else if (a[i][k] + a[j][k] > k2) then
                    k2 := a[i][k] + a[j][k];
            end;
            r := max(r, k1 + k2);
        end;

    write(r);
end.

[Poma][a]

Возможно, если расположить все числа по убыванию, а потом перебором найти максимальные четыре, координаты которых сооставляют прямоугольник, то выйдет немного быстрее чем простой перебор. Но выйгрышь по времени если будет, то будет небольшой и не во всех случаях.

А будет ли вообще это решение правильным?

[Kix.IV]

Сообщение от Poma][a

А будет ли вообще это решение правильным?

Я имел в виду так:

type
  col = record
    x, y, v: integer;
  end;

var
  m: array of col;

И при сортировке координаты остаются те же. Тут лишь отличие в том, что сначала проверяются наибольшие элементы массива.

[Simon1712]

Разобрался, тему можно закрыть...