QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8225. 最小值之和

统计

给定一个长度为 $n-1$ 的非负整数数组 $f$。我们定义 $d_{i,j} = \min_{k=i}^j f_k$。同时对于任意 $1 \le i \le n$, 我们定义 $f'_{i}$ = $\sum_{j=1}^{i-1} d_{j,i-1} + \sum_{j=i}^{n-1} d_{i,j}$。

现在你获得了 $f'_1,f'_2, \cdots, f'_n$ 的值,你需要判断是否存在一个对应的长度为 $n-1$ 的非负整数数组 $f$,满足上述条件。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数,分别表示 $f'_1,f'_2,\cdots,f'_n$。

输出格式

如果存在符合条件非负整数数组 $f$:

第一行输出 'Yes',第二行输出 $n-1$ 个非负整数,第 $i$ 个表示 $f_i$;

如果不存在符合条件非负整数数组 $f$:

第一行输出 'No'。

样例数据

样例输入

3
2 3 3

样例输出

Yes
1 2

子任务

对于全部的数据,满足 $1\le n\le 80,0\le f'_i\le 10^8$。

  • Subtask1(11pts):$n\le 5$,满足性质 A。
  • Subtask2(15pts):$n\le 8$。
  • Subtask3(13pts):$n\le 14$。
  • Subtask4(25pts):$n\le 50$。满足性质 B。
  • Subtask5(17pts):$n\le 50$。
  • Subtask6(19pts):无特殊限制。

性质 A:保证如果存在合法的解,则至少存在一个合法的解满足所有数均小于 $20$。

性质 B:保证如果存在合法的解,则至少存在一个合法的解满足所有数均小于 $50$。