# KDELI - Editorial

Author, Tester, and Editorialist: iceknight1093

TBD

Sorting

# PROBLEM:

K people line up to buy N pastries from a shop. You’re L-th in line.
The pastries have deliciousness values A_1, A_2, \ldots, A_N.

On their turn, a person will always pick the most delicious remaining pastry; then move to the back of the line.
Find the total deliciousness of pastries you buy.

# EXPLANATION:

Let’s sort the array A, so that A_1 \geq A_2 \geq \ldots \geq A_N.
Then, notice that:

• The first person will choose A_1
• The second person will choose A_2
• The third person will choose A_3
\vdots
• The K-th person will choose A_K
• Then, it’s the first person’s turn again, who will pick A_{K+1}
• The second person gets another turn, and picks A_{K+2}
\vdots

In general, the i-th person in line will pick A_i, A_{i+K}, A_{i+2K}, \ldots.
You’re L-th in line, so you’ll pick A_L, A_{L+K}, A_{L+2K}, \ldots
Simply print the sum of these numbers.

Since N can be as large as 2\cdot 10^5 in this task, sorting A needs to be done in \mathcal{O}(N\log N) using an efficient algorithm, such as mergesort or quicksort; \mathcal{O}(N^2) sort algorithms such as bubble sort and insertion sort won’t be fast enough.
The simplest way is to just use your language’s built-in sort function.

# TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n, k, l = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
print(sum(a[l-1::k]))
1 Like