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\% of points, it is possible to iterate over all N projects for each query.

Time Complexity: \mathcal O(NQ)

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

Time Complexity: \mathcal O(N + Q + \max(t_i))


  • 5
    OneYearOld  commented on Nov. 2, 2020, 1:14 p.m.

    If you are still stuck, try this test case out:

    180 1000
    180 500