| Codeforces Round 132 (Div. 2) |
|---|
| Закончено |
На доске нарисовано клетчатое поле из n строк и m столбцов, строки пронумерованы с 1 сверху вниз, а столбцы — с 1 слева направо. Клетку поля на пересечении строки номер i и столбца номер j будем обозначать (i, j).
Шестерку чисел (a, b, c, d, x0, y0) в которой 0 ≤ a, b, c, d назовем крестиком и сопоставим ему множество клеток (x, y) таких, что выполняется хотя бы одно из двух условий:
- |x0 - x| ≤ a и |y0 - y| ≤ b
- |x0 - x| ≤ c и |y0 - y| ≤ d
На рисунке изображен крестик (0, 1, 1, 0, 2, 3) на поле 3 × 4. Ваша задача — найти количество различных шестерок чисел (a, b, c, d, x0, y0), задающих крестики площадью равной s, которые полностью помещаются на заданном поле n × m. Крестик полностью помещается на поле, если любая его клетка находится в пределах поля (то есть для любой принадлежащей крестику клетки (x, y) выполняется 1 ≤ x ≤ n; 1 ≤ y ≤ m). Площадью крестика называется количество принадлежащих ему клеток.
Обратите внимание, что два крестика считаются различными, если упорядоченные шестерки, описывающие их, различаются, даже если эти крестики совпадают как множества клеток.
Входные данные состоят из единственной строки, в которой записаны три целых числа n, m и s (1 ≤ n, m ≤ 500, 1 ≤ s ≤ n·m). Числа разделены пробелом.
Выведите единственное целое число — количество различных шестерок, задающих крестики площадью s и полностью помещающихся на поле размером n × m.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
2 2 1
4
3 4 5
4
В первом примере искомые шестерки: (0, 0, 0, 0, 1, 1), (0, 0, 0, 0, 1, 2), (0, 0, 0, 0, 2, 1), (0, 0, 0, 0, 2, 2).
Во втором примере искомые шестерки: (0, 1, 1, 0, 2, 2), (0, 1, 1, 0, 2, 3), (1, 0, 0, 1, 2, 2), (1, 0, 0, 1, 2, 3).
