Bessie has an array \(a_1, \ldots, a_N\), where \(1 \leq N \leq 300\) and
\(0 \leq a_i \leq 10^9\) for all \(i\). She won't tell you \(a\) itself, but she will
tell you the range of each subarray of \(a\). That is, for each pair of indices
\(i \leq j\), Bessie tells you \(r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]\).
Given these values of \(r\), please construct an array that could have been
Bessie's original array. The values in your array should be in the range
\([-10^9, 10^9]\).

Problem credits: Danny Mittal

SCORING

• Test 5 satisfies \(r_{1,N} \leq 1\).
• Tests 6-8 satisfy \(r_{i,i+1} = 1\) for all \(1 \leq i < N\).
• Tests 9-14 satisfy no additional constraints.

Problem credits: Danny Mittal

The first line contains \(N\).

Another \(N\) lines follow. The \(i\)th of these lines contains the integers
\(r_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}\).

It is guaranteed that there is some array \(a\) with values in the range
\([0, 10^9]\) such that for all \(i \leq j\),
\(r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]\).

Output one line containing \(N\) integers \(b_1, b_2, \ldots, b_N\) in the range
\([-10^9, 10^9]\) representing your array. They must satisfy
\(r_{i, j} = \max b[i\ldots j] - \min b[i\ldots j]\) for all \(i \leq j\).

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > December > Silver