PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Tester & Editorialist: iceknight1093
DIFFICULTY:
1178
PREREQUISITES:
None
PROBLEM:
You have N songs saved on your Dotify app. The i-th song is M_i minutes long and in language L_i.
Find the longest playlist you can make if:
- Exactly K songs from these N should be chosen
- Each song should be of language L
EXPLANATION:
We only care about songs whose language is L.
So, let’s create a list of the lengths of only these songs, say A.
We now want to choose K elements from A such that their sum is as large as possible.
So,
- If the length of A is less than K, choosing K songs is of course impossible.
In this case, the answer is-1. - Otherwise, clearly it’s optimal to choose the largest K elements of A and find their sum.
A simple way to do this is to sort A and then take the sum of its last K elements.
However, the constraints here are small, so a solution in \mathcal{O}(N\cdot K) that repeats “find the maximum element in A, add it to the sum, and then remove it from A”, K times, will also get AC.
TIME COMPLEXITY
\mathcal{O}(N\log N) or \mathcal{O}(N\cdot K) per test case.
CODE:
Editorialist's code (Python, sorting)
for _ in range(int(input())):
n, k, l = map(int, input().split())
songs = []
for i in range(n):
x, y = map(int, input().split())
if y == l: songs.append(x)
songs.sort()
songs = songs[::-1]
if len(songs) < k: print(-1)
else: print(sum(songs[:k]))
Editorialist's code (Python, no sorting)
for _ in range(int(input())):
n, k, l = map(int, input().split())
songs = []
for i in range(n):
x, y = map(int, input().split())
if y == l: songs.append(x)
if len(songs) < k: print(-1)
else:
ans = 0
for i in range(k):
M = max(songs)
ans += M
songs.remove(M)
print(ans)