P8902 [USACO22DEC] Range Reconstruction S

Bessie has an array $a_1, \cdots, a_N$, where $1 \le N \le 300$ and for all $i$ we have $0 \le a_i \le 10^9$. She will not tell you the array $a$ itself, but she will tell you the range of every subarray of $a$. That is, for every pair of indices $i \le j$, Bessie tells you $r_{i,j}= \max a[i \cdots j]− \min a[i \cdots j]$. Given these $r$ values, construct an array that could be Bessie's original array. The values in your array must be in the range $[−10^9,10^9]$.

The first line contains $N$. The next $N$ lines: line $i$ contains the integers $r_{i,i},r_{i,i+1}, \cdots ,r_{i,N}$. It is guaranteed that there exists some array $a$, with values in the range $[0,10^9]$, such that for all $i \le j$, $r_{i,j}= \max a[i \cdots j]−\min a[i\cdots j]$.

Output one line containing $N$ integers $b_1,b_2, \cdots ,b_N$ in the range $[−10^9,10^9]$, representing your array. These numbers must satisfy that for all $i \le j$, $r_{i,j}= \max a[i \cdots j]−\min a[i\cdots j]$.

Sample 1 Explanation For example, $r_{1,3}=\max a[1 \cdots 3]−\min a[1\cdots 3]=3−1=2$. Sample 2 Explanation This sample satisfies the constraints of subtask 1. Sample 3 Explanation This sample satisfies the constraints of subtask 2. Properties of test points - Test point $5$ satisfies $r_{1,N} \le 1$. - Test points $6-8$ satisfy that for all $1 \le i