EKIPA
In a galaxy far, far away, a programming contest is taking place. Your task is to choose the participants!
N students have applied, and each one of them has some knowledge in each of M different categories. Knowledge can be represented as a real number. You can send at most K students to the contest, but no student can compete in more than one category. Multiple students can compete in a single category.
For each student, their knowledge of each category is given.
Choose participants for a contest and categories they will compete in, so that the sum of knowledge is maximal.
Each of the next M lines describes knowledge for one category.
In each line, there are N pairs (i, s), where i is the index of the student, and s is a positive real number representing their knowledge of corresponding category (0 ≤ s ≤ 10). Pairs are given in order of
decreasing knowledge. Students are numbered from 1 to N.
In each line, every student will apear exactly once.
3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2 Output
4.0 4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3 Output
15.0 Description of the first test case:
There are two categories. In the first category, best student is the second one, with knowledge 3.0. He is followed by student numbered 1, with knowledge 0.2, and then number 3, with knowledge 0.1.
Best solution is to choose students 2 and 3, in categories 1 and 2, respectively.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.