CCO '20 P6 - Shopping Plans

View as PDF

Submit solution

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Olympiad: 2020 Day 2, Problem 3

You are shopping from a store that sells a total of N items. The i-th item has a type a_i which is an integer between 1 and M. A feasible shopping plan is a subset of these items such that for all types j, the number of items of type j is in the interval [x_j, y_j].

The i-th item in the store has a cost of c_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 K 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 N, M, and K (1\le N,M,K\le 200\,000). N lines follow, the i-th of which contains two space-separated integers a_i and c_i (1\le a_i\le M, 1\le c_i\le 10^9). M lines follow, the j-th of which contains two space-separated integers x_j and y_j (0\le x_j\le y_j\le N).

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

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

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

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

Output Specification

Output K lines. On the i-th line, output the cost of the i-th cheapest feasible shopping plan, if one exists, or -1 if there are fewer than i 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\} with exactly one item with a cost in \{3,1\}.


Comments


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

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