1974: [USACO 2022 December Contest Silver] Problem 3. Range Reconstruction

Bessie has an array $a_1,\dots ,a_N$, where $1\le N\le 300$ and $0\le a_i\le {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\le j$, Bessie tells you $r_{i,j}=maxa[i\dots j]-mina[i\dots 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]$.

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

It is guaranteed that there is some array a$a$ with values in the range $[0,{10}^9]$ such that for all $i\le j$, $r_{i,j}=maxa[i\dots j]-mina[i\dots j]$.

3
0 2 2
0 1
0

1 3 2