Square Route
Time limit8sMemory limit512 MB
Count all squares formed by grid roads whose row and column spacings vary, given the spacing sequences, across multiple datasets.
- Level
Medium7 of 10
- Topics
- Hash map, Prefix sum, Geometry, Brute force
- Solved
- No attempts yet
Problem
Shinada, a wealthy man who has decided to build a new mansion, is wondering which city to build it in. Shinada is an unusual person who loves squares, so he wants to live in a city with as many squares as possible.
Shinada obtained a list of cities whose roads are laid out in a grid pattern, and decided to count, for each city, the number of squares formed by the roads. Since the spacing between roads is not necessarily uniform, counting squares by hand is a huge task. Therefore, you are asked to write a program that counts the number of squares given information about a grid of roads.
Input
The input consists of multiple datasets, each structured as follows.
N M
h1
h2
...
hN
w1
w2
...
wM
The first line gives two positive integers N, M (1 ≦ N, M ≦ 1500). The following N lines h1, h2, ..., h**N (1 ≦ h**i ≦ 1000) give the north-south spacing between roads. Here h**i is the spacing between the i-th road from the north and the (i + 1)-th road from the north. Similarly, the following M lines w1, ..., w**M (1 ≦ w**i ≦ 1000) give the east-west spacing between roads. Here w**i is the spacing between the i-th road from the west and the (i + 1)-th road from the west. The width of the roads themselves is thin enough that it need not be considered.
Figure D-1: The first dataset
N = M = 0 marks the end of the input and is not included in the datasets.
Output
For each dataset, output the number of squares on one line. For example, the first dataset in the Sample Input contains 6 squares as shown below, so the output for this dataset is 6.
Figure D-2: The squares contained in the first dataset