시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Welcome to your new job at Paris Sightseeing for Groups (PSG). Just like every other employee at PSG, you are in charge of planning trips for groups of people. Your salary will be indexed on your “customer score”. This “customer score” is computed as the maximal h such that there are at least h groups that gave your trip a grade of at least h.
You have prepared several trips for each group according to their specific taste. You know in advance how each group will like each of your trips. However some of these possibilities will take more of your time and some will cost more than others. Since you cannot work 100 hours per week and you have a limited budget, you cannot simply maximize your “customer score” by taking the most liked trip for each group.
You want a program that tells you the maximal customer score that is possible to achieve considering your time and money budgets. Note that you have to plan exactly one trip for each group!
The input comprises several lines, each consisting of integers separated with single spaces.
The output should consist of a single line, whose content is an integer h, the maximal h such that it is possible to give a grade of at least h to at least h groups. If it is not possible to plan a trip for each group then the output should be −1.
3 3 3 1 1 1 1 2 2 0 1 0 3 2 2 3 0 2 0 2 1
1
There is only one assignment possible. We select the first possibility for the groups 1 and 2, and the second possibility for the third group. This amounts to 3 units of time and 3 units of money.
5 5 5 2 0 1 2 4 4 3 2 0 1 3 1 0 2 2 1 0 2 0 1 3 2 1 1 3 0 1 2 2 0 1 2 1 1 3
3
If we select the first possibility for the first group, then we can take the most liked possibility for all other groups. We can therefore serve all groups and ensure that 4 groups have a grade of 3.
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2018 PD번