Загублений список#13113

Загублений список (Розбір)

Лижник з обмеженнями вважає трасу типу придатною саме тоді, коли x \ge i і y \ge j, тож a_{i,j} — це сума c_{x,y} за всіма x \ge i, y \ge j: — це двовимірна суфіксна сума . Вона складається з двох одновимірних суфіксних сум, уздовж рівнів крутизни і уздовж рівнів довжини, і кожну з них однозначно обертаємо: якщо s_j = v_j + v_{j+1} + \ldots + v_m, то v_j = s_j - s_{j+1} (де s_{m+1} = 0). Отже, цілі числа з потрібними сумами завжди існують і єдині:

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

де поза таблицею (для i = n + 1 або j = m + 1) дорівнює . Результати опитування несуперечливі тоді й лише тоді, коли всі ці c_{x, y} невід'ємні; інакше відповідь . Перевіряйте кожну пару , зокрема x = n та y = m, і не беріть значення з попереднього тестового випадку як нульову межу.

Кожне c_{x, y} лежить між -2 \cdot 10^9 та 2 \cdot 10^9, тож 32-бітного int достатньо.

Складність на тестовий випадок.