The semester is finally over and the summer holiday is coming. However, as part of your university's graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.To simplify the problem, let's represent the mountain where trees are to be planted with an. N from left to right. The elevation of the cell in the. . Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are. . Please help your leader calculate the maximum possible number of cells in such a rectangle so that he'll know how many trees will be planted.
The semester is finally over and the summer holiday is coming. However, as part of your university's graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain. To simplify the problem, let's represent the mountain where trees are to be planted with an N times N N×N grid. Let's number the rows 1 1 to N N from top to bottom, and number the columns 1 1 to N N from left to right. The elevation of the cell in the i i-th row and j j-th column is denoted by a_{i,j} a i,j . Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are (x_1,y_1) (x 1 ,y 1 ) and (x_2,y_2) (x 2 ,y 2 ), then the condition |a_{i,j} - a_{k,l}| le M ∣a i,j −a k,l ∣≤M must hold for x_1 le i,k le x_2, y_1 le j,l le y_2 x 1 ≤i,k≤x 2 , y 1 ≤j,l≤y 2 . Please help your leader calculate the maximum possible number of cells in such a rectangle so that he'll know how many trees will be planted.
