### [A. Garland](https://mirror.codeforces.com/gym/558367/problem/A)↵
↵
<spoiler summary = "Understand the Problem">↵
The problem asks us to turn on all four colored light bulbs in a garland, with the restriction that a bulb can only be switched if its color differs from the one switched previously. The goal is to find the minimum number of operations needed to turn all bulbs on, or determine if it’s impossible.↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial ">↵
↵
If u observe there are only Five possible configurations of the bulbs:↵
↵
1. **AAAA**: All bulbs are of the same color. This makes it impossible to turn on all bulbs, as you cannot alternate between different colors. ↵
**Answer**: `-1`.↵
↵
2. **AAAB**: Three bulbs are of the same color, and one bulb is different. In this case, it's impossible to turn all bulbs on in just 4 moves because at least one bulb must be turned on, off, and on again, making the minimum number of operations **6**. ↵
**Answer**: `6`.↵
↵
3. **AABB**: There are two pairs of bulbs with the same colors. In this configuration, you can alternate between the two pairs of bulbs and turn them all on in exactly **4 operations**. ↵
**Answer**: `4`.↵
↵
4. **AABC**: Two bulbs share the same color, while the other two are different. Similarly, you can alternate between different-colored bulbs, and all bulbs can be turned on in **4 operations**. ↵
**Answer**: `4`.↵
↵
5. **ABCD**: All four bulbs are of different colors. There are no restrictions in this case, and you can easily turn all bulbs on in **4 operations**. ↵
**Answer**: `4`.↵
↵
**Summary** ↵
For the **AAAA** case, the answer is `-1`. (max appearance = 4) ↵
For the **AAAB** case, the answer always `6`. (Max appearance = 3)↵
For the **AABB**, **AABC**, and **ABCD** cases, the answer is `4`. (Max appearance = 2 or 1)↵
</spoiler>↵
↵
<spoiler summary="Code ">↵
```↵
from collections import Counter↵
↵
def solve():↵
s = input()↵
mx = max(Counter(s).values())↵
↵
if mx == 4:↵
print(-1)↵
elif mx == 2 or mx == 1:↵
print(4)↵
else:↵
print(6)↵
↵
for _ in range(int(input())):↵
solve()↵
↵
↵
```↵
↵
↵
</spoiler>↵
↵
↵
### [B. Detective Book](https://mirror.codeforces.com/gym/558367/problem/B)↵
↵
↵
<spoiler summary=" Understand the Problem ">↵
↵
In this problem, Ivan is reading a detective book where each page introduces a mystery explained on a later page. The goal is to determine how many days it will take for him to read the entire book, given that he can only read a sequence of pages until all mysteries encountered are explained.↵
↵
↵
### How does Ivan decide when to stop?↵
↵
Ivan stops reading at the end of a day **only** when all the mysteries he has read so far are fully explained by that point.↵
↵
↵
### Example Walkthrough:↵
↵
Consider ↵
```↵
1 3 3 6 7 6 8 8 9↵
```↵
↵
- Page 1 explains the mystery on page 1.↵
- Page 2 introduces a mystery that gets explained on page 3.↵
- Page 3 introduces a mystery that gets explained on page 3.↵
- Page 4 introduces a mystery that gets explained on page 6.↵
- And so on...↵
↵
↵
**Day 1**:↵
- Ivan starts with page 1, which is explained by itself. He can stop here because there's no pending mystery.↵
- So, **Day 1 ends** after page 1.↵
↵
**Day 2**:↵
- Ivan starts with page 2. Page 2 introduces a mystery explained by page 3.↵
- He reads page 3, which also introduces a mystery explained by page 3 (already read).↵
- Now all mysteries (from page 2 and 3) are explained, so he can stop here.↵
- **Day 2 ends** after page 3.↵
↵
**Day 3**:↵
- Ivan starts reading from page 4. It introduces a mystery explained by page 6.↵
- He reads pages 4, 5, 6, 7, and 8, because all these pages introduce mysteries that are explained only up to page 8.↵
- After page 8, all mysteries are explained, so he can stop.↵
- **Day 3 ends** after page 8.↵
↵
**Day 4**:↵
- Ivan reads page 9, which explains itself. There are no pending mysteries.↵
- **Day 4 ends** after page 9.↵
↵
↵
↵
Thus, the answer is **4 days**.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Once you understand the problem, the solution becomes straightforward. The key is to iterate through the list of pages while keeping track of the highest page number (or "mystery") Ivan must read to resolve all mysteries encountered so far. Each day, Ivan continues reading until he reaches this maximum mystery page. Whenever the current day’s page number matches the maximum mystery, it means all mysteries are explained, and Ivan can stop for the day. By counting these stopping points, you determine how many days it takes for Ivan to finish the book.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
```↵
def solve():↵
n = int(input())↵
nums = [int(x) for x in input().split()]↵
mystery = 1↵
ans = 0↵
i = 0↵
for day in range(1,n+1):↵
mystery = max(nums[i] , mystery)↵
if day == mystery:↵
ans += 1↵
↵
i += 1↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
### [C. Points on Plane](https://mirror.codeforces.com/gym/558367/problem/C)↵
↵
<spoiler summary="Understand the problem">↵
↵
↵
The task is to place \(n\) chips on a 2D plane, where chips can only be placed at integer coordinates. The cost of placing a chip at point \((x, y)\) is calculated as \( |x| + |y| \), which is the **Manhattan distance** from the origin to the point.↵
↵
You must place the chips such that:↵
↵
1. The Euclidean distance between each pair of chips is strictly greater than 1.↵
1. The maximum cost across all placed chips is minimized.↵
↵
The goal is to find the minimum possible cost for placing \(n\) chips while satisfying the distance constraint.↵
↵
Here’s the consistent format for the example including \(n = 5\):↵
↵
#### Example:↵
↵
- For \(n = 1\), you can place the chip at the origin \((0, 0)\) with a cost of \(0\).↵
- For \(n = 3\), you can place chips at \((-1, 0)\), \((0, 1)\), and \((1, 0)\) with a cost of \(1\).↵
- For \(n = 5\), you can place chips at \((-1, 1)\), \((1, 1)\), \((-1, -1)\), \((1, -1)\), and \((0, 2)\) with a cost of \(2\).↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
Suppose, the answer is k↵
. What's the maximum number of chips we can place? Firstly, the allowed points (x,y)↵
to place chips are such that |x|+|y|≤k↵
. We can group them by x↵
-coordinate: for x=k↵
there is only one y=0↵
, for x=k−1↵
possible y↵
are −1,0,1↵
; for x=k−2↵
possible y↵
are in segment [−2,…,2]↵
and so on. For x=0↵
possible y↵
are in [−k,…,k]↵
. The negative x↵
-s are the same.↵
↵
Let's calculate the maximum number of chips we can place at each "row": for x=k↵
it's 1↵
; for x=k−1↵
there are three y↵
-s, but since we can't place chips at the neighboring y↵
-s, we can place at most 2↵
chips; for x=k−2↵
we have 5↵
places, but can place only 3↵
chips; for x=0↵
we have 2k+1↵
places, but can occupy only k+1↵
points.↵
↵
In total, for x∈[0,…,k]↵
we can place at most 1+2+⋯+(k+1)=(k+1)(k+2)2↵
chips. Analogically, for x∈[−k,…,−1]↵
we can place at most 1+2+⋯+k=k(k+1)2↵
chips.↵
↵
In total, we can place at most (k+1)(k+2)2+k(k+1)2=(k+1)2↵
chips with cost at most k↵
. Note that (k+1)2↵
can actually be reached since the distance between chips on the different rows is greater than 1↵
.↵
↵
So, to solve our task, it's enough to find minimum k↵
such that (k+1)2≥n↵
that can be done with Binary Search.↵
↵
Or we can calculate k=⌈n−−√⌉−1↵
. Note that n−−√↵
can lose precision, since n↵
is cast to double before taking the square root (for example, 975461057789971042↵
transforms to 9.754610577899711⋅1017=975461057789971100↵
when converted to double). So you should either cast long long to long double (that consists of 80↵
bits in some C++ compilers) or check value k+1↵
as a possible answer.↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code1">↵
```↵
↵
def solve():↵
n = int(input())↵
↵
def check(k):↵
return (k + 1) ** 2 >= n↵
↵
↵
↵
l = 0 ↵
r = 10**9↵
ans = float("inf")↵
↵
while l <= r:↵
mid = (l + r) // 2↵
if check(mid):↵
ans = min(mid,ans)↵
r = mid - 1↵
else:↵
l = mid + 1 ↵
↵
print(ans)↵
for _ in range(int(input())):↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Code2">↵
```↵
import math↵
↵
def solve():↵
n = int(input())↵
↵
ans = math.isqrt(n-1)↵
print(ans)↵
↵
for _ in range(int(input())):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
### [D. Good String](https://mirror.codeforces.com/gym/558367/problem/D)↵
↵
<spoiler summary="Tutorial">↵
Let's analyze when the string is good. Suppose it is t1t2…tk↵
.↵
↵
The cyclic shifts of this string are tkt1t2…tk−1↵
and t2t3…tkt1↵
. We get the following constraints for a good string: tk=t2↵
, t1=t3↵
, t2=t4↵
, ..., tk−2=tk↵
, tk−1=t1↵
. If the string has odd length, then all characters should be equal to each other; otherwise, all characters on odd positions should be equal, and all characters on even positions should be equal.↵
↵
Now, since there are only 10↵
different types of characters, we can brute force all possible combinations of the first and the second character of the string we want to obtain (there are only 100↵
of them) and, for each combination, greedily construct the longest possible subsequence of s↵
beginning with those characters in O(n)↵
.</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
def solve(s, x, y):↵
res = 0↵
for c in s:↵
if int(c) == x:↵
res += 1↵
x, y = y, x ↵
if x != y and res % 2 == 1:↵
res -= 1↵
return res↵
↵
↵
↵
for _ in range(int(input())):↵
s = input()↵
ans = 0↵
for x in range(10):↵
for y in range(10):↵
ans = max(ans, solve(s, x, y))↵
print(len(s) - ans)↵
```↵
</spoiler>↵
↵
### [E. Playlist ](https://mirror.codeforces.com/gym/558367/problem/E)↵
↵
<spoiler summary="Problem">↵
↵
The problem is about choosing up to k songs from a playlist, where each song has a length and a beauty. The goal is to maximize the pleasure of listening, which is calculated as the sum of the selected song lengths multiplied by the smallest beauty among those songs.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
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.↵
↵
We can solve this problem by first sorting the songs in descending order of beauty, so we prioritize songs with higher beauty values. As we process each song, we maintain a running total of the song lengths using a min-heap. If the number of selected songs exceeds `k`, we remove the smallest length to keep the total as large as possible. At each step, we compute the pleasure by multiplying the current total length by the beauty of the song we're considering, and we update the maximum pleasure accordingly. This approach ensures we maximize the pleasure by balancing the sum of lengths and the minimum beauty.↵
</spoiler>↵
↵
- Code by [user:kalki75,2024-10-17] ↵
↵
<spoiler summary="Code">↵
```↵
from heapq import heappop, heappush↵
↵
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)↵
```↵
</spoiler>↵
↵
↵
<spoiler summary = "Understand the Problem">↵
The problem asks us to turn on all four colored light bulbs in a garland, with the restriction that a bulb can only be switched if its color differs from the one switched previously. The goal is to find the minimum number of operations needed to turn all bulbs on, or determine if it’s impossible.↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial ">↵
↵
If u observe there are only Five possible configurations of the bulbs:↵
↵
1. **AAAA**: All bulbs are of the same color. This makes it impossible to turn on all bulbs, as you cannot alternate between different colors. ↵
**Answer**: `-1`.↵
↵
2. **AAAB**: Three bulbs are of the same color, and one bulb is different. In this case, it's impossible to turn all bulbs on in just 4 moves because at least one bulb must be turned on, off, and on again, making the minimum number of operations **6**. ↵
**Answer**: `6`.↵
↵
3. **AABB**: There are two pairs of bulbs with the same colors. In this configuration, you can alternate between the two pairs of bulbs and turn them all on in exactly **4 operations**. ↵
**Answer**: `4`.↵
↵
4. **AABC**: Two bulbs share the same color, while the other two are different. Similarly, you can alternate between different-colored bulbs, and all bulbs can be turned on in **4 operations**. ↵
**Answer**: `4`.↵
↵
5. **ABCD**: All four bulbs are of different colors. There are no restrictions in this case, and you can easily turn all bulbs on in **4 operations**. ↵
**Answer**: `4`.↵
↵
**Summary** ↵
For the **AAAA** case, the answer is `-1`. (max appearance = 4) ↵
For the **AAAB** case, the answer always `6`. (Max appearance = 3)↵
For the **AABB**, **AABC**, and **ABCD** cases, the answer is `4`. (Max appearance = 2 or 1)↵
</spoiler>↵
↵
<spoiler summary="Code ">↵
```↵
from collections import Counter↵
↵
def solve():↵
s = input()↵
mx = max(Counter(s).values())↵
↵
if mx == 4:↵
print(-1)↵
elif mx == 2 or mx == 1:↵
print(4)↵
else:↵
print(6)↵
↵
for _ in range(int(input())):↵
solve()↵
↵
↵
```↵
↵
↵
</spoiler>↵
↵
↵
### [B. Detective Book](https://mirror.codeforces.com/gym/558367/problem/B)↵
↵
↵
<spoiler summary=" Understand the Problem ">↵
↵
In this problem, Ivan is reading a detective book where each page introduces a mystery explained on a later page. The goal is to determine how many days it will take for him to read the entire book, given that he can only read a sequence of pages until all mysteries encountered are explained.↵
↵
↵
### How does Ivan decide when to stop?↵
↵
Ivan stops reading at the end of a day **only** when all the mysteries he has read so far are fully explained by that point.↵
↵
↵
### Example Walkthrough:↵
↵
Consider ↵
```↵
1 3 3 6 7 6 8 8 9↵
```↵
↵
- Page 1 explains the mystery on page 1.↵
- Page 2 introduces a mystery that gets explained on page 3.↵
- Page 3 introduces a mystery that gets explained on page 3.↵
- Page 4 introduces a mystery that gets explained on page 6.↵
- And so on...↵
↵
↵
**Day 1**:↵
- Ivan starts with page 1, which is explained by itself. He can stop here because there's no pending mystery.↵
- So, **Day 1 ends** after page 1.↵
↵
**Day 2**:↵
- Ivan starts with page 2. Page 2 introduces a mystery explained by page 3.↵
- He reads page 3, which also introduces a mystery explained by page 3 (already read).↵
- Now all mysteries (from page 2 and 3) are explained, so he can stop here.↵
- **Day 2 ends** after page 3.↵
↵
**Day 3**:↵
- Ivan starts reading from page 4. It introduces a mystery explained by page 6.↵
- He reads pages 4, 5, 6, 7, and 8, because all these pages introduce mysteries that are explained only up to page 8.↵
- After page 8, all mysteries are explained, so he can stop.↵
- **Day 3 ends** after page 8.↵
↵
**Day 4**:↵
- Ivan reads page 9, which explains itself. There are no pending mysteries.↵
- **Day 4 ends** after page 9.↵
↵
↵
↵
Thus, the answer is **4 days**.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Once you understand the problem, the solution becomes straightforward. The key is to iterate through the list of pages while keeping track of the highest page number (or "mystery") Ivan must read to resolve all mysteries encountered so far. Each day, Ivan continues reading until he reaches this maximum mystery page. Whenever the current day’s page number matches the maximum mystery, it means all mysteries are explained, and Ivan can stop for the day. By counting these stopping points, you determine how many days it takes for Ivan to finish the book.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
```↵
def solve():↵
n = int(input())↵
nums = [int(x) for x in input().split()]↵
mystery = 1↵
ans = 0↵
i = 0↵
for day in range(1,n+1):↵
mystery = max(nums[i] , mystery)↵
if day == mystery:↵
ans += 1↵
↵
i += 1↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
### [C. Points on Plane](https://mirror.codeforces.com/gym/558367/problem/C)↵
↵
<spoiler summary="Understand the problem">↵
↵
↵
The task is to place \(n\) chips on a 2D plane, where chips can only be placed at integer coordinates. The cost of placing a chip at point \((x, y)\) is calculated as \( |x| + |y| \), which is the **Manhattan distance** from the origin to the point.↵
↵
You must place the chips such that:↵
↵
1. The Euclidean distance between each pair of chips is strictly greater than 1.↵
1. The maximum cost across all placed chips is minimized.↵
↵
The goal is to find the minimum possible cost for placing \(n\) chips while satisfying the distance constraint.↵
↵
Here’s the consistent format for the example including \(n = 5\):↵
↵
#### Example:↵
↵
- For \(n = 1\), you can place the chip at the origin \((0, 0)\) with a cost of \(0\).↵
- For \(n = 3\), you can place chips at \((-1, 0)\), \((0, 1)\), and \((1, 0)\) with a cost of \(1\).↵
- For \(n = 5\), you can place chips at \((-1, 1)\), \((1, 1)\), \((-1, -1)\), \((1, -1)\), and \((0, 2)\) with a cost of \(2\).↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
Suppose, the answer is k↵
. What's the maximum number of chips we can place? Firstly, the allowed points (x,y)↵
to place chips are such that |x|+|y|≤k↵
. We can group them by x↵
-coordinate: for x=k↵
there is only one y=0↵
, for x=k−1↵
possible y↵
are −1,0,1↵
; for x=k−2↵
possible y↵
are in segment [−2,…,2]↵
and so on. For x=0↵
possible y↵
are in [−k,…,k]↵
. The negative x↵
-s are the same.↵
↵
Let's calculate the maximum number of chips we can place at each "row": for x=k↵
it's 1↵
; for x=k−1↵
there are three y↵
-s, but since we can't place chips at the neighboring y↵
-s, we can place at most 2↵
chips; for x=k−2↵
we have 5↵
places, but can place only 3↵
chips; for x=0↵
we have 2k+1↵
places, but can occupy only k+1↵
points.↵
↵
In total, for x∈[0,…,k]↵
we can place at most 1+2+⋯+(k+1)=(k+1)(k+2)2↵
chips. Analogically, for x∈[−k,…,−1]↵
we can place at most 1+2+⋯+k=k(k+1)2↵
chips.↵
↵
In total, we can place at most (k+1)(k+2)2+k(k+1)2=(k+1)2↵
chips with cost at most k↵
. Note that (k+1)2↵
can actually be reached since the distance between chips on the different rows is greater than 1↵
.↵
↵
So, to solve our task, it's enough to find minimum k↵
such that (k+1)2≥n↵
that can be done with Binary Search.↵
↵
Or we can calculate k=⌈n−−√⌉−1↵
. Note that n−−√↵
can lose precision, since n↵
is cast to double before taking the square root (for example, 975461057789971042↵
transforms to 9.754610577899711⋅1017=975461057789971100↵
when converted to double). So you should either cast long long to long double (that consists of 80↵
bits in some C++ compilers) or check value k+1↵
as a possible answer.↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code1">↵
```↵
↵
def solve():↵
n = int(input())↵
↵
def check(k):↵
return (k + 1) ** 2 >= n↵
↵
↵
↵
l = 0 ↵
r = 10**9↵
ans = float("inf")↵
↵
while l <= r:↵
mid = (l + r) // 2↵
if check(mid):↵
ans = min(mid,ans)↵
r = mid - 1↵
else:↵
l = mid + 1 ↵
↵
print(ans)↵
for _ in range(int(input())):↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Code2">↵
```↵
import math↵
↵
def solve():↵
n = int(input())↵
↵
ans = math.isqrt(n-1)↵
print(ans)↵
↵
for _ in range(int(input())):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
### [D. Good String](https://mirror.codeforces.com/gym/558367/problem/D)↵
↵
<spoiler summary="Tutorial">↵
Let's analyze when the string is good. Suppose it is t1t2…tk↵
.↵
↵
The cyclic shifts of this string are tkt1t2…tk−1↵
and t2t3…tkt1↵
. We get the following constraints for a good string: tk=t2↵
, t1=t3↵
, t2=t4↵
, ..., tk−2=tk↵
, tk−1=t1↵
. If the string has odd length, then all characters should be equal to each other; otherwise, all characters on odd positions should be equal, and all characters on even positions should be equal.↵
↵
Now, since there are only 10↵
different types of characters, we can brute force all possible combinations of the first and the second character of the string we want to obtain (there are only 100↵
of them) and, for each combination, greedily construct the longest possible subsequence of s↵
beginning with those characters in O(n)↵
.</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
def solve(s, x, y):↵
res = 0↵
for c in s:↵
if int(c) == x:↵
res += 1↵
x, y = y, x ↵
if x != y and res % 2 == 1:↵
res -= 1↵
return res↵
↵
↵
↵
for _ in range(int(input())):↵
s = input()↵
ans = 0↵
for x in range(10):↵
for y in range(10):↵
ans = max(ans, solve(s, x, y))↵
print(len(s) - ans)↵
```↵
</spoiler>↵
↵
### [E. Playlist ](https://mirror.codeforces.com/gym/558367/problem/E)↵
↵
<spoiler summary="Problem">↵
↵
The problem is about choosing up to k songs from a playlist, where each song has a length and a beauty. The goal is to maximize the pleasure of listening, which is calculated as the sum of the selected song lengths multiplied by the smallest beauty among those songs.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
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.↵
↵
We can solve this problem by first sorting the songs in descending order of beauty, so we prioritize songs with higher beauty values. As we process each song, we maintain a running total of the song lengths using a min-heap. If the number of selected songs exceeds `k`, we remove the smallest length to keep the total as large as possible. At each step, we compute the pleasure by multiplying the current total length by the beauty of the song we're considering, and we update the maximum pleasure accordingly. This approach ensures we maximize the pleasure by balancing the sum of lengths and the minimum beauty.↵
</spoiler>↵
↵
- Code by [user:kalki75,2024-10-17] ↵
↵
<spoiler summary="Code">↵
```↵
from heapq import heappop, heappush↵
↵
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)↵
```↵
</spoiler>↵
↵
