← 返回题目列表

AtCoder · abc462_e

E. 交替成本

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

分数: 450 点

问题陈述

给你整数 A,B,X,Y.

一块被放置在二维平面上。最初,该工件位于坐标处 (0,0).

您可以执行以下操作零次或多次:

  • 设该块的当前坐标为 (x,y)。将棋子移动到其中一个坐标 (x-1,y),(x+1,y),(x,y-1),(x,y+1).

的成本 k第一次操作 (k \geq 1) 取决于奇偶校验 k,如下:

  • If k 为奇数:设当前棋子的坐标为 (x,y)。搬家费用 (x-1,y) or (x+1,y) is A,以及搬到的成本 (x,y-1) or (x,y+1) is B.
  • If k 为偶数:设当前棋子的坐标为 (x,y)。搬家费用 (x-1,y) or (x+1,y) is B,以及搬到的成本 (x,y-1) or (x,y+1) is A.

求将棋子移动到坐标所需的最小总成本 (X,Y).

T 给出了测试用例;逐一解决。

约束

  • 1\le T\le 2\times 10^5
  • 1\le A,B\le 10^9
  • -10^9\le X,Y\le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

的 i-th (1\le i\le T)测试用例 \text{case}_i 按以下格式给出:

A B X Y

输出

按顺序输出测试用例的答案,每个答案在单独的行上。


示例输入 1

5
1 2 -1 2
8 5 0 0
7 13 9 4
1 1 0 100
31 9 -74 -60

示例输出 1

4
0
103
100
1332

考虑第一个测试用例。

以下动作需要花费 4 总计:

  • 将棋子从 (0,0) to (-1,0)。这需要花费 1.
  • 将棋子从 (-1,0) to (-1,1)。这需要花费 1.
  • 将棋子从 (-1,1) to (-1,2)。这需要花费 2.

无法将棋子移动到 (-1,2) 总成本低于 4,所以输出 4 在第一行。