A. Garland
B. Detective Book
C. Points on Plane
E. Playlist
The intuition behind this problem is to maximize the total pleasure by carefully balancing two things: the total length of the songs you choose and the beauty of those songs. Since pleasure depends on both, the trick is to first focus on beauty because it acts as a multiplier. Higher beauty means we get a bigger boost in pleasure, so it makes sense to start by considering the most beautiful songs first.
However, we also need to manage the total length of the songs we pick, since adding longer songs can increase the total pleasure. But we can only select up to k songs, so if we reach the limit, we should drop the shortest song to keep the sum of lengths as large as possible. This way, we get the best combination of beauty and length to maximize the pleasure.
Code by Kalki75
n, k = map(int,input().split())
nums = []
for _ in range(n): t, b = map(int,input().split()) nums.append([t,b])
nums.sort(reverse = True, key= lambda x: x[1])
heap = [] ans = 0 total = 0
for i in range(n): time, beauty = nums[i] total += time
if len(heap) < k:
heappush(heap,(time,beauty))
else:
min_time, min_beauty = heappop(heap)
heappush(heap,(time,beauty))
total -= min_time
ans = max(ans,total*beauty)print(ans) ```
