 Contest

MEDIUM

# PROBLEM:

There are NN items in the bakery. Each item’s cost is cost[i]cost[i] and the delivery charge is delivery_cost[i]delivery_cost[i] for ii = 00 to NN respectively. The chef wants to select exactly MM items to sell in a way that the total cost is maximized.

The total cost for any set of items is `the sum of costs of those items + (minimum delivery cost among those items * total no. of items)`. Help the chef find the maximum cost for MM items.

# EXPLANATION

There are two major ways to think about this problem. One is a backtracking-based approach and the other is a heap-based approach.

## 1. Backtracking:

The main idea of this approach is to try all the possibilities using recursion and use memorization to overcome repeated computations.

### SOLUTION

``````import sys
min_d = 10 ** 7

# set recursion limit
sys.setrecursionlimit(10 ** 7)

# argument mid_d_cost maps to the minimum delivery cost
# among the current set of items in the bag.
def recurce(i, bag_size, min_d_cost):
# base cases
if bag_size == 0: return min_d_cost * m
if i >= n: return 0

if (i, bag_size, min_d_cost) in DP:
return DP[(i, bag_size, min_d_cost)]
k = max(
cost[i] + recurce(i+1, bag_size-1, min(min_d_cost, cost_d[i])),
recurce(i+1, bag_size, min_d_cost)
)
DP[(i, bag_size, min_d_cost)] = k
return k

t = int(input())
for _ in range(t):
n, m = map(int, input().split())
cost = list(map(int, input().split()))
cost_d = list(map(int, input().split()))
DP = {}
print(recurce(0, m, min_d))
``````

Time complexity: `O(m * n)`
Space Complexity: `O(m * n * n)`

## 2. Heap:

Solution author: nihal_47

The idea of this solution is to first sort the data based on delivery costs, Pickup `m-1` items with the highest prices using a heap. And then select one item based on delivery `cost + price` that maximizes the total cost.

### SOLUTIONS

``````import heapq
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
li = list(map(int, input().split()))
data = []
temp = list(map(int, input().split()))

for i in range(n):
data.append([temp[i], li[i]])

data.sort(key=lambda x: x)
ans = 0
psum =  * (n+1)
pq = []
heapq.heapify(pq)
sum = 0
for i in range(n-1, 0, -1):
if (i >= (n - (m-1))):
sum += data[i]
psum[i] = sum
heapq.heappush(pq, data[i])
else:
heapq.heappush(pq, data[i])
sum += data[i]
sum -= heapq.heappop(pq)
psum[i] = sum
for i in range(n):
if (i+m-1 < n):
ans = max(ans, data[i] * m + (psum[i+1] + data[i]))
print(ans)
``````

Time Complexity: `O(n * log n)`
Space Complexity: `O(n)`

Note: The first solution will not pass subtask 2 in the original problem but it was a good approach to know about, hence we decided to include that in the editorial.

Feel free to share other approaches.