DMOPC '19 Contest 2 P4 - A Greedy Problem

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.1s
Java 0.6s
PyPy 2 0.3s
PyPy 3 0.3s
Memory limit: 128M

Problem type

Jack is doing a programming contest. There are N problems in this contest and the contest will last a total of T minutes. The i-th problem will take Jack exactly t_i minutes to solve. Having an aversion to certain problem types such as dynamic programming, Jack wonders how many subsets of problems he can solve within q_i minutes if he decides that he definitely wants to solve problem a_i and problem b_i. More formally, Jack wants to determine the number of subsets of problems that contain problem a_i and problem b_i whose sum of solve times is less than or equal to q_i. Since this number may be very large, output it modulo 10^9+7. Two subsets are different if there is a problem in one of the subsets that does not appear in the other subset.

Help Jack answer a total of Q of these queries.


In all subtasks,
2 \le N, T, Q \le 2\,000
1 \le t_i, q_i \le T
1 \le a_i, b_i \le N
a_i \neq b_i

Subtask 1 [20%]

N, T \le 100

Subtask 2 [20%]

Q \le 10

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains three space-separated integers, N T Q
The next line contains N space-separated integers, t_1, t_2, \ldots t_N
The next Q lines contain three space-separated integers, a_i b_i q_i

Output Specification

Output Q lines. The i-th line should contain the answer to the i-th query.

Sample Input

3 90 2
20 30 40
1 2 50
1 3 90

Sample Output



  • 2
    p1geon  commented on Oct. 21, 2019, 2:46 p.m.

    Python users can't even pass batch 1 with the intended solution.

    • -1
      Zeyu  commented on Oct. 21, 2019, 5:19 p.m.

      Seems fine to me, worst case was less than 0.3s in pypy2.

      • 2
        p1geon  commented on Oct. 21, 2019, 5:22 p.m.

        Time limit was 0.1s before.