Editorial for DMPG '17 B5 - Hackathons - Olympiads Online Judge

Editorial for DMPG '17 B5 - Hackathons

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For $60\%$ $60 %$ of points, it is possible to iterate over all $N$ $N$ projects for each query.

Time Complexity: $\mathcal O(NQ)$ $O (N Q)$

For the remaining $40\%$ $40 %$ of points, we can generate a prefix maximum array, namely we can create an array $A$ $A$ , where $A[i]$ $A [i]$ stores the maximum wow factor of all projects that take $i$ $i$ minutes or less. Each query can then be answered in constant time.

Time Complexity: $\mathcal O(N + Q + \max(t_i))$ $O (N + Q + max (t_{i}))$

Comments

5
OneYearOld commented on Nov. 2, 2020, 1:14 p.m.
If you are still stuck, try this test case out:

Copy
2 180 1000 180 500 2 178 300