Час

12:00:24
11 Лютого 2012
ACM-ICPC Thailand Southern Region Programming Contest 2011
Залишилося: 2 години 0 хвилин
Кінець: 11.02.2012 15:00
Лідер: Informatimukas
П`ятірка за тиждень 22
Залишилося: 9 годин 0 хвилин
Кінець: 11.02.2012 22:00
Лідер: NuM
Версія для друку

Будинок

   Новий росіянин Вітек приватизував ділянку у Міждолинні розміром m квадратів з півночі на південь та n квадратів із заходу на схід. Він вирішив побудувати в межах цієї ділянки будинок розміром a квадратів з півночі на південь та b – з заходу на схід. Деякі квадрати радіоактивні, і Вітек не бажає на них будувати будинок.  Крім того, Вітек хоче, щоб відстані від стін до границь ділянки вимірювались цілим числом квадратів. Довго обирав він місце для будинку, але так і не вибрав – занадто багато варіантів. А скільки? Розпочав наш герой рахувати, але не зумів – погано математику вчив. Допоможіть йому.


Технічні умови

   Вхідні дані

   Напишите програму, яка зчитує числа m, n, a, b, k, де m, n – розміри ділянки, a та b – розміри будинку, k – кількість радіоактивних квадратів, а потім k пар чисел i та j, які не повторюються і визначають координати радіоактивних квадратів. Відомо, що 1a m 5000, 1b n 5000, 0k m*n, 1i m, 1j n

   Вихідні дані

   Вивести шукану кількість способів розташування будинку.


Інформація про задачу

Ліміт часу: 3 секунди
Ліміт пам`яті: 128 MB
Бали за пройдений тест: 3.84615
Складність: 21% 38/48
Автор: Непомнящий Григорій
Джерело: Турнір Чемпіонів 2010, Вінниця 2010
Класифікація: Динамічне програмування

Приклад

Приклад вхідних даних

5 7 2 4 3 2 5 3 3 3 6

Приклад вихідних даних

5


← Оранжерея Список задач Велосипед →