201441: [AtCoder]ARC144 B - Gift Tax

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

You are given positive integers $a$ and $b$ such that $a\leq b$, and a sequence of positive integers $A = (A_1, A_2, \ldots, A_N)$.

On this sequence, you can perform the following operation any number of times (possibly zero):

  • Choose distinct indices $i, j$ ($1\leq i, j \leq N$). Add $a$ to $A_i$ and subtract $b$ from $A_j$.

Find the maximum possible value of $\min(A_1, A_2, \ldots, A_N)$ after your operations.

Constraints

  • $2\leq N\leq 3\times 10^5$
  • $1\leq a\leq b\leq 10^9$
  • $1\leq A_i\leq 10^{9}$

Input

Input is given from Standard Input in the following format:

$N$ $a$ $b$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the maximum possible value of $\min(A_1, A_2, \ldots, A_N)$ after your operations.


Sample Input 1

3 2 2
1 5 9

Sample Output 1

5

Here is one way to achieve $\min(A_1, A_2, A_3) = 5$.

  • Perform the operation with $i = 1, j = 3$. $A$ becomes $(3, 5, 7)$.
  • Perform the operation with $i = 1, j = 3$. $A$ becomes $(5, 5, 5)$.

Sample Input 2

3 2 3
11 1 2

Sample Output 2

3

Here is one way to achieve $\min(A_1, A_2, A_3) = 3$.

  • Perform the operation with $i = 1, j = 3$. $A$ becomes $(13, 1, -1)$.
  • Perform the operation with $i = 2, j = 1$. $A$ becomes $(10, 3, -1)$.
  • Perform the operation with $i = 3, j = 1$. $A$ becomes $(7, 3, 1)$.
  • Perform the operation with $i = 3, j = 1$. $A$ becomes $(4, 3, 3)$.

Sample Input 3

3 1 100
8 5 6

Sample Output 3

5

You can achieve $\min(A_1, A_2, A_3) = 5$ by not performing the operation at all.


Sample Input 4

6 123 321
10 100 1000 10000 100000 1000000

Sample Output 4

90688

Input

题意翻译

给定 $a$,$b$($a\le b$)。每次操作选定 $i$,$j$,$A_i\gets A_i+a$,$A_j\gets A_j-b$。 问 $A$ 数列的最小值的最大可能值?

加入题单

上一题 下一题 算法标签: