DMPG '17 B5 - Hackathons

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Python 3.0s
Memory limit: 64M

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

Roger is going to a hackathon again! Unlike last time, he has prepared a possible list of projects and has an estimate of how long each project takes, as well as its wow factor. However, his partner, Joey, wishes to go for very long coffee breaks, and thus gives him Q queries to answer: if they only have T minutes to complete their project, what is the maximum wow factor of their project.

Note: at hackathons (or at least the ones in this question), only a single project is done.

Subtasks

For all subtasks, 1 \le t_i, w_i, T \le 10^6.

Subtask 1 [60%]

1 \le N \le 10^3

1 \le Q \le 10^3

Subtask 2 [40%]

1 \le N \le 10^6

1 \le Q \le 10^6

Input Specification

Line 1: An integer, N, the number of projects Roger has prepared.
Lines 2 \dots N + 1: Two space separated integers, t_i, and w_i, the amount of time required for the i^{th} project and its wow factor respectively.
Line N + 2: An integer, Q, the number of queries Joey gives.
Line N + 3 \dots N + Q + 2: An integer, T, the maximum time Roger and Joey have.

Output Specification

Q space-separated integers, the answer to each query.

Sample Input

3
1 3
8 9
2 2
3
10
8
3

Sample Output

9
9
3

Explanation for Sample Output

If Roger and Joey have 10 minutes, they have enough time to complete projects 1, 2, and 3, and the maximum wow factor is 9.
If they have 8 minutes, they still have time to complete all three projects, so the maximum wow factor is still 9.
If they have 3 minutes, they can only complete projects 1 and 3, and the maximum wow factor of these two projects is 3.


Comments


  • 4
    alexzhang  commented on Aug. 14, 2018, 12:23 a.m. edit 2

    Note: at hackathons (or at least the ones in this question), only a single project is done.

    they have enough time to complete projects 1, 2, and 3.

    I am actually really confused right now. Are they doing multiple projects like the example, or a single project?

    EDIT: oh wait never mind, I see what happens now