I am trying to solve this question: https://www.codechef.com/problems/TADELIVE
Andy and Bob are the only two delivery men of Pizza-chef store. Today, the store received N orders. It's known that the amount of tips may be different when handled by different delivery man. More specifically, if Andy takes the ith order, he would be tipped Ai dollars and if Bob takes this order, the tip would be Bi dollars.
They decided that they would distribute the orders among themselves to maximize the total tip money. One order will be handled by only one person. Also, due to time constraints Andy cannot take more than X orders and Bob cannot take more than Y orders. It is guaranteed that X + Y is greater than or equal to N, which means that all the orders can be handled by either Andy or Bob.
Please find out the maximum possible amount of total tip money after processing all the orders
- 1 ≤ N ≤ 10⁵
- 1 ≤ X, Y ≤ N
- X + Y ≥ N
- 1 ≤ Ai, Bi ≤ 10⁴
I have used a dynamic programming approach:
""" https://www.codechef.com/problems/TADELIV] """ """ https://www.codechef.com/problems/TADELIV] """ from functools import lru_cache @lru_cache(maxsize=None) def optimal_sum(x, y, i): if i >= len(a): return 0 if x == 0: return sum(b[i:]) if y == 0: return sum(a[i:]) sum_with_a = a[i] + optimal_sum(x-1, y, i+1) sum_with_b = b[i] + optimal_sum(x, y-1, i+1) return max(sum_with_a, sum_with_b) n, x, y = map(int, input().split()) a = [int(i) for i in input().split()] b = [int(i) for i in input().split()] ans = optimal_sum(x, y, 0) print(ans)
Sadly this timed out :( How do I make it run faster?