GCEA - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N Pekómon, the i-th of them has catching difficulty A_i.
To catch them, you can buy either Normal Pekóballs (cost x each, need A_i of them to catch the i-th Pekómon) or Master Pekóballs (cost y each, only need 1 to catch anything).

What’s the minimum amount you need to spend to be able to catch every Pekómon?

EXPLANATION:

Let’s look at a single Pekómon, with catching difficulty A_i.
To catch it, we have two options:

  • Use A_i Normal Pekóballs, which cost x each for a total cost of A_i\cdot x.
  • Use a single Master Pekóball, which costs y.

So, the best we can do is \min(y, A_i\cdot x).
Simply repeat this reasoning for each of the N Pekómon and sum up to get the overall minimum cost.
That is, the answer is

\sum_{i=1}^N \min(y, A_i\cdot x)

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        ans += min(y, a[i]*x)
    print(ans)