DMOPC '15 Contest 1 P2 - Itami and Squad

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Itami has been chosen as one of L officers to lead recon squads into an unknown land! To determine the members of each squad, the leaders will draft soldiers from a pool of soldiers of initial size N.

Itami has designated a number B_i for each soldier, representing the strength of the i-th soldier in battle. Of course, he knows that every squad leader would like to have the strongest squad possible, and will therefore pick the best soldiers available to them (a soldier i is considered to be better than another soldier j if B_i > B_j). If there are multiple "best" soldiers, the squad leader will pick a random one — it doesn't matter exactly which one they choose.

Since the army is a well-structured organization, the order of drafting will be determined by seniority. Itami is ranked R-th out of the L squad leaders. In the drafting process, the most senior squad leader will pick a soldier, then the second in seniority will pick a soldier out of the remaining pool, and so on. If there are still soldiers remaining after the most junior squad leader has made his pick, the process will repeat until there are no more remaining.

The strength of a squad is defined as the sum of strengths of all its members. Itami would like to know what the strength of his squad would be, following this process.

Input Specification

The first line of input will contain N (1 \le N \le 10\,000), the number of soldiers, L (1 \le L \le 100), the number of squad leaders and R (1 \le R \le L), Itami's rank amongst the squad leaders, each separated by one space.

The second line will contain N space-separated integers, B_1, \dots, B_N (1 \le B_i \le 1\,000), denoting the strength of the i-th soldier.

Output Specification

Output one integer, the strength of Itami's squad following the process described above.

Sample Input 1

5 2 2
2 7 1 4 3

Sample Output 1


Explanation for Sample Output 1

Itami has second pick in this case. Following the drafting process, his senior will pick the soldiers with strengths 7, 3, 1, and he will pick the soldiers with strengths 4 and 2. Therefore the total strength of his squad will be 4 + 2 = 6.

Sample Input 2

3 4 4
1000 1000 1000

Sample Output 2


Explanation for Sample Output 2

Poor Itami! He doesn't even get to pick a single soldier since he is fourth pick and there are only 3 soldiers available. Now he'll be sulking in a corner, jealously looking at the other squads with their superhuman soldiers.

Sample Input 3

9 1 1
1 1 1 1 1 1 1 1 1

Sample Output 3


Explanation for Sample Output 3

Itami is the only squad leader! Now he has a large squad full of inexperienced soldiers.


  • 0
    charliezhao  commented on Oct. 13, 2015, 11:18 p.m.

    The way I answered this question was very simple, I tried to make it as efficient as I could, but it seems that my program always take more than 1 second to solve test case 6.

    • 0
      Xyene  commented on Oct. 13, 2015, 11:25 p.m.

      I've reviewed the test case in question, and it fits within the given constraints. A Python solution exists that can run within the given time limit.

    • 4
      kobortor  commented on Oct. 13, 2015, 11:25 p.m.

      When there's a whole page of other people getting 100/100 ACs, it's probably something wrong with your code, not the testcases.