MAKEMONEY - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: utkarsh_25dec
Testers: IceKnight1093, tabr
Editorialist: IceKnight1093

DIFFICULTY:

1101

PREREQUISITES:

None

PROBLEM:

Chef has N bags, the i-th with A_i \leq X coins. He can pay C coins to increase the number of coins in the i-th bag to X.

Find the maximum possible value of \sum A_i - cost, where cost is the number of coins paid by Chef when performing operations.

EXPLANATION:

Let’s look at the i-th bag. We can either increase the coins in it or choose not to.

  • If we don’t do anything, this bag gives us A_i coins.
  • If we increase it, this bag gives us X coins but also a cost of C, for a total of X-C.

Since we’re free to perform operations as many times as we want to, we can simply take the maximum of the above two values; and then repeat this for every index.
That is, the final answer is

\sum_{i=1}^N \max(A_i, X-C)

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x, c = map(int, input().split())
    a = list(map(int, input().split()))
    print(sum(max(y, x-c) for y in a))
1 Like