Lost List#13113

Lost List (Editorial)

A skier with limits finds the slope type suitable exactly when x \ge i and y \ge j, so a_{i,j} is the sum of c_{x,y} over all x \ge i, y \ge j: is the two-dimensional suffix sum of . It consists of two one-dimensional suffix sums, one along the steepness levels and one along the length levels, and each of them is inverted uniquely: if s_j = v_j + v_{j+1} + \ldots + v_m, then v_j = s_j - s_{j+1} (with s_{m+1} = 0). Hence the integers with the required sums always exist and are unique:

c_{x, y} = a_{x, y} - a_{x+1, y} - a_{x, y+1} + a_{x+1, y+1},

where is outside the table (for i = n + 1 or j = m + 1). The survey is consistent if and only if all these c_{x, y} are non-negative; otherwise the answer is . Check every pair , including x = n and y = m, and do not reuse values from a previous test case as the zero border.

Every c_{x, y} lies between -2 \cdot 10^9 and 2 \cdot 10^9, so a 32-bit int suffices.

The complexity is per test case.