Enough Profit, Few Enough People
Each scheme has a profit and needs a number of people. Count the subsets of schemes
whose total profit is AT LEAST P and whose total people is AT MOST G.
Print the count modulo 1000000007.
schemes (profit=2 people=2) (profit=3 people=2), P = 3, G = 5 -> 2
The two qualifying subsets are {2nd} with profit 3, and {1st, 2nd} with profit 5 and
4 people. {1st} has profit 2, which is short.
## Two constraints pulling opposite ways
People is an ordinary capacity: AT MOST, so exceeding it is fatal and the axis is bounded
by G.
Profit is a floor: AT LEAST, so exceeding it is GOOD. That is the difference, and it is what makes the profit axis unusual.
## Capping the profit axis
A profit axis running to the sum of all profits would be large and, more importantly,
pointless: once the total profit reaches P, how far past it you are can never matter
again, because the condition is already satisfied and nothing can unsatisfy it.
So CAP the profit index at P:
new profit index = min(P, current + this profit)
The state P then means "profit at least P", absorbing every larger total into one
entry. The table is (G+1) x (P+1) regardless of how large the profits are.
This is the same principle as problem 492's residue state, in a different disguise: the
state records exactly what the objective can still distinguish. Past P the objective
cannot distinguish anything, so the states merge.
## The recurrence
dp[0][0] = 1
for each scheme (profit, people):
for g from G down to people:
for p from P down to 0:
dp[g][min(P, p + profit)] += dp[g - people][p]
answer = sum over g of dp[g][P]
Both loops descend, because each scheme is used at most once and this is 0/1.
## Reading the answer
Sum dp[g][P] over every g from 0 to G, not just dp[G][P].
The people count is an at-most constraint, so subsets using fewer than G people qualify
and each sits in its own row. Reading one row only counts the subsets that use exactly
G people, and on the sample that gives 0.
## The zero-profit case
P = 0 means every subset qualifies on profit, including the empty one, since 0 is at
least 0. (profit=0 people=1) (profit=0 people=1) with P = 0, G = 2 answers 4, all
four subsets.
The capped index handles it: min(0, anything) is 0, so every state is already the
accepting state. A solution that special-cases P = 0 usually forgets the empty subset
and answers 3.
## Cost
Time O(n G P). Space O(G P).