DMPG '17 B5 - Hackathons - DMOJ: Modern Online Judge

DMPG '17 B5 - Hackathons

Points: 7 (partial)

Time limit: 1.0s

Python 3.0s

Memory limit: 64M

Author:

Problem type

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$ $Q$ queries to answer: if they only have $T$ $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.

Constraints

For all subtasks:

$1 \le t_i, w_i, T \le 10^6$ $1 \leq t_{i}, w_{i}, T \leq 10^{6}$

Subtask 1 [60%]

$1 \le N, Q \le 10^3$ $1 \leq N, Q \leq 10^{3}$

Subtask 2 [40%]

$1 \le N, Q \le 10^6$ $1 \leq N, Q \leq 10^{6}$

Input Specification

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

Output Specification

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

Sample Input

Copy

Sample Output

Copy

9
9
3

Explanation for Sample Output

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

Comments

1

julian33 commented on Nov. 1, 2020, 7:17 p.m.

I believe fast I/O is necessary for this problem

-5

kevinyang commented on Nov. 1, 2020, 11:04 p.m.

Water is wet

This comment is hidden due to too much negative feedback. Show it anyway.

4

alexzhang commented on Aug. 14, 2018, 4: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