Rectangles
Time limit1sMemory limit128 MB
Count axis-aligned rectangles on an n by m grid of points whose perimeter is at least p.
- Level
Easy3 of 10
- Topics
- Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
How many rectangles can you find in the figure below?

In the figure above we can find 6 rectangles of size , 4 of size , 3 of size , 2 of size , 2 of size , and 1 of size , which gives 18 in total. Here we count only rectangles whose vertices lie on grid points (the intersections of the vertical and horizontal line segments) and whose four sides are all vertical or horizontal. The grid above has dimensions .
And how many such rectangles with a perimeter of at least 6 are there? For this grid there are 12 of them.
Given a grid of dimensions and a lower bound on the perimeter, count the rectangles whose vertices lie on grid points, whose four sides are vertical or horizontal, and whose perimeter is at least .
Input
The first and only line of the standard input contains three integers , , and (, ), representing the dimensions of the grid and the lower bound on the perimeter of the rectangles.
Output
On the first line of the standard output, print a single integer: the number of rectangles of the grid whose vertices lie on grid points, whose four sides are vertical or horizontal, and whose perimeter is at least .