Editorial for DMPG '17 B5 - Hackathons - DMOJ: Modern 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)$ ~\mathcal O(NQ)~

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))$ ~\mathcal 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:

2 180 1000 180 500 2 178 300