021. Земельный комитет

(Время - 1 сек., память - 16 Мб)

Земельный комитет города принял решение о сдаче в аренду части муниципальной территории, имеющей форму прямоугольника размером H на W километров. Стоимость аренды каждого квадратного участка 1 x 1 км была определена с учётом локальных условий, и занесена в таблицу.

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

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

Требуется написать программу, позволяющую как можно более эффективно рассчитывать стоимость аренды для N запросов. В каждом запросе требуется определить общую стоимость участков внутри прямоугольной группы с противоположными углами, расположенными в элементах таблицы (ai, bi) и (ci, di).

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

В первой строке входного файла input.txt записаны числа H, W, N (1 ≤ H, W ≤ 100, 1 ≤ N ≤ 1000000). В следующих H строках содержится по W чисел (стоимости участков находятся в диапазоне от 0 до 10000). Далее идут N строк с числами ai bi ci di (1 ≤ ai ≤ ci ≤ H, 1 ≤ bi ≤ di ≤ W).

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

В выходной файл output.txt нужно вывести N чисел, по одному числу в строке.

Пример

input.txt

output.txt

1

2 3 1
5 1 2
6 7 3
2 1 2 3

16

Разбор

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

Программа на Паскале

var

  s : array[0..100,0..100] of longint;

  h, w, i, j, a, b, c, d : integer;

  n, k, x : longint;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(h,w,n);

  for i:=0 to w do s[i,0]:=0;

  for j:=0 to h do s[0,j]:=0;

  for j:=1 to h do

    for i:=1 to w do begin

      read(x);

      s[i,j]:=x+s[i-1,j]+s[i,j-1]-s[i-1,j-1]

    end;

  for k:=1 to n do begin

    read(a,b,c,d);

    write(s[d,c]-s[d,a-1]-s[b-1,c]+s[b-1,a-1]);

    if k<n then writeln

  end;

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 4-й тур

Тематика

Динамическое программирование

Примерная сложность

41%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=470

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 24.05.2012