Задача C. Локальные минимумы ≡

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Дана последовательность из N целых чисел a1, a2, …, aN. Назовём элемент ai локальным минимумом радиуса k, если он меньше, чем по крайней мере k элементов непосредственно справа и k элементов непосредственно слева от него.

Например, в последовательности 5 4 1 4 5 6 число 1 является единственным локальным минимумом с радиусами 1 и 2.

По данной последовательности и числу k требуется определить все локальные минимумы радиуса k.

Формат входного файла

Входной файла содержит целые числа N k, за которыми следует N целых чисел ai.

Формат выходного файла

Выходной файл должен содержать число M — количество локальных минимумов радиуса k, и затем сами минимумы в том порядке, в котором они встречаются в исходной последовательности.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ k ≤ N, 0 ≤ ai ≤ 10000.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
5 1
3 2 3 1 3

2
2 1
2 
6 2
1 2 3 1 3 1

0

Задача K. Максимальная сумма ≡

Автор:Седьмая Всероссийская Командная олимпиада школьников по программированию
Входной файл: max.in   Ограничение времени:2 сек
Выходной файл: max.out   Ограничение памяти:64 Мб

Условие

Сегодня на страницах газеты "Математический досуг" была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.

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

Формат входного файла

На первой строке входного файла записаны два целых числа m и n. Далее следует описание таблицы - m строк, каждая из которых содержит по n целых чисел ai,j.

Формат выходного файла

На первой строке выходного файла выведите целое число s - максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: x1, y1, x2, y2 - координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь x - номер строки, а y - номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Ограничения

2 ≤ m, n ≤ 300; −104 ≤ ai,j ≤ 104

Примеры тестов

№ Входной файл (max.in) Выходной файл (max.out)
1 
2 3
1 1 1
1 1 1
 
6
1 1 2 3
2 
5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2
 
8
3 1 5 3

Задача S. Максимальная тройка ≡

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:4 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

В данном двумерном целочисленном массиве a размером N × N требуется найти три элемента, сумма которых максимальна. При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.

Формат входного файла

Входной файл содержит число N, за которым следует N2 чисел
a1,1 a1,2…a1,N
a2,1 a2,2…a2,N
 … 
aN,1 aN,2…aN,N
 — элементы массива.

Формат выходного файла

Выходной файл должен содержать единственное число — максимальную сумму. При N = 1 следует вывести единственный элемент матрицы.

Ограничения

1 ≤ N ≤ 2000, 0 ≤ ai,j ≤ 109,

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2
1 2
3 4
 
9
0.035s 0.004s 13