question.txt

you are a zoo keeper, You wanna keep animals to be healthy (not overweight) so you apply a diet plan.
Problem:
An animal has intial weight S at the start, For every day, you can choose to lose weight (a[i]) or have food (b[i]) or , but you have to make sure every day animal doesnt exceed T (target weight)
for N days plan, how many possbile combinations can have
condition
・1 ≦ N ≦ 35
・1 ≦ Ai, Bi ≦ 1,000,000,000 (1 ≦ i ≦ N)
・(sum of A_i) < S ≦ T ≦ 1,000,000,000
sample in
2 10 20
5 6
3 10
out: 3
sample in
8 300 400
9 39
48 38
21 10
14 45
32 20
32 48
9 7
19 16
out: 194

solution.py

from bisect import bisect_right

# input
input_line = input()
[n, s, t] = [int(x) for x in input_line.split()]
vs = []
for _ in range(n):
    input_line = input()
    vs.append([int(x) for x in input_line.split()])
    
def solve(vs, w):
  n = len(vs)
  g = n // 2

  # table
  ps = [0]
  for i in range(g):
    [a,b] = vs[n-i-1]
    ps = [max(0,v-a) for v in ps] + [v+b for v in ps]
  ps.sort()

  # dp
  def run(i, w):
    if w < 0: 
      return 0
    if i == n - g:
      return bisect_right(ps, w)
    return run(i+1, w+vs[i][0]) + run(i+1, w-vs[i][1])

  return run(0,w)

print(solve(vs,t-s))