#PU1256. USACO 2022 December Contest, Silver — Problem 3. Range Reconstruction

USACO 2022 December Contest, Silver — Problem 3. Range Reconstruction

USACO 2022 December Contest, Silver — Problem 3. Range Reconstruction

题目描述

Bessie has an array a1,…,aNa_1, \ldots, a_N, where 1≤N≤3001 \leq N \leq 300 and 0≤ai≤1090 \leq a_i \leq 10^9 for all ii. She won't tell you aa itself, but she will tell you the range of each subarray of aa. That is, for each pair of indices i≤ji \leq j, Bessie tells you ri,j=max⁡a[i…j]−min⁡a[i…j]r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]. Given these values of rr, please construct an array that could have been Bessie's original array. The values in your array should be in the range [−109,109][-10^9, 10^9].

输入格式

The first line contains NN. Another NN lines follow. The iith of these lines contains the integers ri,i,ri,i+1,…,ri,Nr_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}. It is guaranteed that there is some array aa with values in the range [0,109][0, 10^9] such that for all i≤ji \leq j, ri,j=max⁡a[i…j]−min⁡a[i…j]r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j].

输出格式

(见题面原文)

数据范围

Test 5 satisfies r1,N≤1r_{1,N} \leq 1. Tests 6-8 satisfy ri,i+1=1r_{i,i+1} = 1 for all 1≤i<N1 \leq i < N. Tests 9-14 satisfy no additional constraints. Problem credits: Danny Mittal

样例

样例 1

3
0 2 2
0 1
0
1 3 2
For example, $r_{1, 3} = \max a[1\ldots 3] - \min a[1\ldots 3] = 3 - 1 = 2$.

样例 2

3
0 1 1
0 0
0
0 1 1
This example satisfies the constraints for subtask 1.

样例 3

4
0 1 2 2
0 1 1
0 1
0
1 2 3 2
This example satisfies the constraints for subtask 2.

样例 4

4
0 1 1 2
0 0 2
0 2
0
1 2 2 0