A15790. Two Tanks
编程题
普及/提高-
知识点
题目描述
There are two water tanks, the first one fits $a$ liters of water, the second one fits $b$ liters of water. The first tank has $c$ ( $0 \le c \le a$ ) liters of water initially, the second tank has $d$ ( $0 \le d \le b$ ) liters of water initially.
You want to perform $n$ operations on them. The $i$ -th operation is specified by a single non-zero integer $v_i$ . If $v_i > 0$ , then you try to pour $v_i$ liters of water from the first tank into the second one. If $v_i < 0$ , you try to pour $-v_i$ liters of water from the second tank to the first one.
When you try to pour $x$ liters of water from the tank that has $y$ liters currently available to the tank that can fit $z$ more liters of water, the operation only moves $\min(x, y, z)$ liters of water.
For all pairs of the initial volumes of water $(c, d)$ such that $0 \le c \le a$ and $0 \le d \le b$ , calculate the volume of water in the first tank after all operations are performed.
You want to perform $n$ operations on them. The $i$ -th operation is specified by a single non-zero integer $v_i$ . If $v_i > 0$ , then you try to pour $v_i$ liters of water from the first tank into the second one. If $v_i < 0$ , you try to pour $-v_i$ liters of water from the second tank to the first one.
When you try to pour $x$ liters of water from the tank that has $y$ liters currently available to the tank that can fit $z$ more liters of water, the operation only moves $\min(x, y, z)$ liters of water.
For all pairs of the initial volumes of water $(c, d)$ such that $0 \le c \le a$ and $0 \le d \le b$ , calculate the volume of water in the first tank after all operations are performed.
输入格式
The first line contains three integers $n, a$ and $b$ ( $1 \le n \le 10^4$ ; $1 \le a, b \le 1000$ ) — the number of operations and the capacities of the tanks, respectively.
The second line contains $n$ integers $v_1, v_2, \dots, v_n$ ( $-1000 \le v_i \le 1000$ ; $v_i \neq 0$ ) — the volume of water you try to pour in each operation.
The second line contains $n$ integers $v_1, v_2, \dots, v_n$ ( $-1000 \le v_i \le 1000$ ; $v_i \neq 0$ ) — the volume of water you try to pour in each operation.
输出格式
For all pairs of the initial volumes of water $(c, d)$ such that $0 \le c \le a$ and $0 \le d \le b$ , calculate the volume of water in the first tank after all operations are performed.
Print $a + 1$ lines, each line should contain $b + 1$ integers. The $j$ -th value in the $i$ -th line should be equal to the answer for $c = i - 1$ and $d = j - 1$ .
Print $a + 1$ lines, each line should contain $b + 1$ integers. The $j$ -th value in the $i$ -th line should be equal to the answer for $c = i - 1$ and $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
说明/提示
Consider $c = 3$ and $d = 2$ from the first example:
- The first operation tries to move $2$ liters of water from the second tank to the first one, the second tank has $2$ liters available, the first tank can fit $1$ more liter. Thus, $\min(2, 2, 1) = 1$ liter is moved, the first tank now contains $4$ liters, the second tank now contains $1$ liter.
- The second operation tries to move $1$ liter of water from the first tank to the second one. $\min(1, 4, 3) = 1$ liter is moved, the first tank now contains $3$ liters, the second tank now contains $2$ liter.
- The third operation tries to move $2$ liter of water from the first tank to the second one. $\min(2, 3, 2) = 2$ liters are moved, the first tank now contains $1$ liter, the second tank now contains $4$ liters.
There's $1$ liter of water in the first tank at the end. Thus, the third value in the fourth row is $1$ .
- The first operation tries to move $2$ liters of water from the second tank to the first one, the second tank has $2$ liters available, the first tank can fit $1$ more liter. Thus, $\min(2, 2, 1) = 1$ liter is moved, the first tank now contains $4$ liters, the second tank now contains $1$ liter.
- The second operation tries to move $1$ liter of water from the first tank to the second one. $\min(1, 4, 3) = 1$ liter is moved, the first tank now contains $3$ liters, the second tank now contains $2$ liter.
- The third operation tries to move $2$ liter of water from the first tank to the second one. $\min(2, 3, 2) = 2$ liters are moved, the first tank now contains $1$ liter, the second tank now contains $4$ liters.
There's $1$ liter of water in the first tank at the end. Thus, the third value in the fourth row is $1$ .