← 返回题目列表

Codeforces · 1809/E

E. 两个坦克

中文机器翻译题面 查看原题

有两个水箱,第一个可容纳 $$$a$$$ 升水,第二个可容纳 $$$b$$$ 升水。第一个水箱最初有 $$$c$$$ ($$$0 \le c \le a$$$) 升水,第二个水箱最初有 $$$d$$$ ($$$0 \le d \le b$$$) 升水。

您想要对它们执行 $$$n$$$ 操作。第 $$$i$$$ 操作由单个非零整数 $$$v_i$$$ 指定。如果 $$$v_i > 0$$$,那么您尝试将第一个水箱中的 $$$v_i$$$ 升水倒入第二个水箱中。如果 $$$v_i < 0$$$,则尝试将 $$$-v_i$$$ 升水从第二个水箱倒入第一个水箱。

当您尝试将 $$$x$$$ 升水从当前可用 $$$y$$$ 升的水箱倒入可容纳 $$$z$$$ 升水的水箱中时,该操作仅移动 $$$\min(x, y, z)$$$ 升水。

对于所有成对的初始水体积 $$$(c, d)$$$,使得 $$$0 \le c \le a$$$ 和 $$$0 \le d \le b$$$,计算执行所有操作后第一个水箱中的水体积。

输入

第一行包含三个整数 $$$n、a$$$ 和 $$$b$$$ ($$$1 \le n \le 10^4$$$; $$$1 \le a, b \le 1000$$$) — 分别是操作次数和储罐容量。

第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$-1000 \le v_i \le 1000$$$; $$$v_i \neq 0$$$) - 您在每次操作中尝试倒入的水量。

输出

对于所有成对的初始水体积 $$$(c, d)$$$,使得 $$$0 \le c \le a$$$ 和 $$$0 \le d \le b$$$,计算执行所有操作后第一个水箱中的水体积。

打印 $$$a + 1$$$ 行,每行应包含 $$$b + 1$$$ 整数。第 $$$i$$$ 行中的第 $$$j$$$ 值应等于 $$$c = i - 1$$$ 和 $$$d = j - 1$$$ 的答案。

示例

输入 #1

3 4 4
-2 1 2

输出 #1

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

输入 #2

3 9 5
1 -2 2

输出 #2

0 0 0 0 0 0 
0 0 0 0 0 1 
0 1 1 1 1 2 
1 2 2 2 2 3 
2 3 3 3 3 4 
3 4 4 4 4 5 
4 5 5 5 5 6 
5 6 6 6 6 7 
6 7 7 7 7 8 
7 7 7 7 8 9

注意

考虑第一个示例中的 $$$c = 3$$$ 和 $$$d = 2$$$:

- 第一个操作尝试将 $$$2$$$ 升水从第二个水箱转移到第一个水箱,第二个水箱有 $$$2$$$ 升可用,第一个水箱可以容纳 $$$1$$$ 升。因此,$$$\min(2, 2, 1) = 1$$$ 升被移动,第一个水箱现在包含 $$$4$$$ 升,第二个水箱现在包含 $$$1$$$ 升。
- 第二次操作尝试将 $$$1$$$ 升水从第一个水箱移至第二个水箱。 $$$\min(1, 4, 3) = 1$$$ 升已移动,第一个水箱现在包含 $$$3$$$ 升,第二个水箱现在包含 $$$2$$$ 升。
- 第三次操作尝试将 $$$2$$$ 升水从第一个水箱移至第二个水箱。 $$$\min(2, 3, 2) = 2$$$ 升被移动,第一个水箱现在包含 $$$1$$$ 升,第二个水箱现在包含 $$$4$$$ 升。

最后的第一个水箱里有 $$$1$$$ 升水。因此,第四行中的第三个值是$$$1$$$。