문제
N개의 원소로 이루어진 배열 a는 a1, …, aN로 이루어졌다 (0 ≤ ai ≤ 109).
배열 a 자체를 알 수는 없지만, 각 인덱스 쌍 i ≤ j에 대해 ri,j = max a[i … j] − min a[i … j]와 같은 배열 a의 하위 배열의 범위가 주어진다. 이러한 r 값을 토대로 배열 a를 구성하자.
배열 a의 각 원소의 범위는 [−109, 109]이다.
입력
첫 번째 줄에 N이 입력된다 (1≤N≤300).
이어서 N줄에 걸쳐 하위 배열 ri,i, ri,i+1, …, ri,N가 입력된다.
출력
첫 줄에 ri,j = max a[i … j] − min a[i … j ] (i ≤ j)를 충족시키는 [−109, 109] 범위내의 정수들로 이루어진 배열 a를 출력하시오.
예제1
입력
3
0 2 2
0 1
0
출력
1 3 2
예제2
입력
3
0 1 1
0 0
0
출력
0 1 1
예제3
입력
4
0 1 2 2
0 1 1
0 1
0
출력
1 2 3 2
예제4
입력
4
0 1 1 2
0 0 2
0 2
0
출력
1 2 2 0
힌트
출처
USACO 2022 December Silver