CCO '20 P6 - Shopping Plans

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type
Canadian Computing Olympiad: 2020 Day 2, Problem 3

You are shopping from a store that sells a total of NN items. The ii-th item has a type a_ia_i which is an integer between 11 and MM. A feasible shopping plan is a subset of these items such that for all types jj, the number of items of type jj is in the interval [x_j, y_j][x_j, y_j].

The ii-th item in the store has a cost of c_ic_i, and the cost of a shopping plan is the sum of the costs of items in the plan. You are interested in the possible costs of feasible shopping plans. Find the costs of the KK cheapest feasible shopping plans. Note that if there are two different shopping plans with the same cost, they should be counted separately in the output.

Input Specification

The first line consists of three space-separated integers NN, MM, and KK (1 \le N, M, K \le 200\,000)(1 \le N, M, K \le 200\,000). NN lines follow, the ii-th of which contains two space-separated integers a_ia_i and c_ic_i (1 \le a_i \le M, 1 \le c_i \le 10^9)(1 \le a_i \le M, 1 \le c_i \le 10^9). MM lines follow, the jj-th of which contains two space-separated integers x_jx_j and y_jy_j (0 \le x_j \le y_j \le N)(0 \le x_j \le y_j \le N).

For 5 of the 25 available marks, x_j = y_j = 1x_j = y_j = 1 and N, M, K \le 4\,000N, M, K \le 4\,000.

For an additional 5 of the 25 available marks, x_j = y_j = 1x_j = y_j = 1 and N, M, c_i \le 4\,000N, M, c_i \le 4\,000.

For an additional 5 of the 25 available marks, x_j = y_j = 1x_j = y_j = 1.

For an additional 5 of the 25 available marks, x_j = 0x_j = 0.

Output Specification

Output KK lines. On the ii-th line, output the cost of the ii-th cheapest feasible shopping plan, if one exists, or -1 if there are fewer than ii feasible shopping plans.

Sample Input 1

5 2 7
1 5
1 3
2 3
1 6
2 1
1 1
1 1

Output for Sample Input 1

4
6
6
7
8
9
-1

Explanation of Output for Sample Input 1

A feasible shopping plan must combine exactly one item with a cost in \{5,3,6\}\{5,3,6\} with exactly one item with a cost in \{3,1\}\{3,1\}.


Comments


  • 7
    bqi343  commented on May 31, 2020, 10:46 a.m.

    Looks like an extension of USACO Dec 2016 - Robotic Cow Herd (my solution here)