Problem:


ネットカフェ

あなたはネットカフェを経営しています。今日あなたは、顧客に指摘され続けている問題を解決しようと取り組んでいます。その問題とは、店舗の本棚の単行本が巻数順に並んでおらず、目的の単行本を探しだすのが面倒だという苦情です。

あなたの店舗で一番巻数の多い単行本は「名探偵 赤ベコ」（通称「赤ベコ」）です。あまりに長編なので、特別な本棚を「赤ベコ」のために用意しました。

単行本の各巻の重さと厚さは様々で、本棚の各段の幅と、各段に並べることができる本の重さの上限も様々です。あなたは、次の条件を満足するように本棚に本を並べることにしました。

 1 巻からある巻までの「赤ベコ」が本棚に並んでいる。

 それぞれの段には、巻数順に（途中で抜けている巻がないように）本が並ぶ。

 各段に並べる本の重さの合計が、その段で定められた重さの上限を超えない。

 各段に並べる本の厚さの合計が、その段の幅を超えない。

これらの条件を満たしたとき，この本棚に最大で何巻まで「赤ベコ」を並べることができるかを求めるプログラムを作成してください。

入力

入力は以下の形式で与えられる。

M N
w1 t1
w2 t2
:
wM tM
c1 b1
c2 b2
:
cN bN

最初の１行に「赤ベコ」の巻数 M (1 ≤ M ≤ 200000) と本棚の段数 N (1 ≤ N ≤ 15) が与えられる。続く M 行に、「赤ベコ」の単行本 i 巻目の重さ wi (1 ≤ wi ≤ 100) と厚さ ti (1 ≤ ti ≤ 100) を表す整数が与えられる。続く N 行に、本棚の i 段目の重さの上限 ci (1 ≤ ci ≤ 108)と幅 bi (1 ≤ bi ≤ 108) を表す整数が与えられる。

出力

本棚に並べることができる最大の「赤ベコ」巻数を１行に出力する。

入出力例

入力例１

3 4
2 2
3 3
4 4
3 3
4 4
1 1
2 2

出力例１

3

入力例２

2 2
1 2
2 1
2 1
2 1

 出力例２

0

入力例３

3 2
1 2
2 2
2 1
3 3
2 2

 出力例３

2

入力例４

3 2
1 2
2 1
2 2
2 2
3 3

出力例４

3



Sample input:
3 4
2 2
3 3
4 4
3 3
4 4
1 1
2 2


Sample output:
3

Submission status: Accepted

Solution code:
import bisect
m, n = map(int, input().split())
w = [tuple(map(int, input().split())) for _ in range(m)]
w, t = map(list,zip(*w))
for i in range(1, m):
    w[i] += w[i - 1]
    t[i] += t[i - 1]
c = [tuple(map(int, input().split())) for _ in range(n)]
c, b = map(list,zip(*c))
a = {}
a[tuple(range(n))] = -1
for _ in range(n):
    an = [(k,a[k]) for k in a]
    a = {}
    for x in an:
        for p in x[0]:
            if x[1] != -1:i = min(bisect.bisect_right(w, c[p] + w[x[1]], x[1]), bisect.bisect_right(t, b[p] + t[x[1]], x[1])) - 1
            else:i = min(bisect.bisect_right(w, c[p]), bisect.bisect_right(t, b[p])) - 1
            y = list(x[0])
            y.remove(p)
            y = tuple(y)
            if y in a:a[y] = max(a[y], i)
            else:a[y] = i
print(max([a[i] for i in a]) + 1)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
from itertools import accumulate

def main():
  
  m, n = map(int, input().split())
  books = list(list(map(int, input().split())) for _ in range(m))
  ws = list(accumulate([0] + [book[0] for book in books]))
  ts = list(accumulate([0] + [book[1] for book in books]))
  shelf = list(list(map(int, input().split())) for _ in range(n))
  
  dic = {}
  rest = 2 ** n - 1
  def search(index, num):
    wlim, tlim = shelf[num]
    wind = br(ws, ws[index] + wlim)
    tind = br(ts, ts[index] + tlim)
    return min(wind, tind) - 1
  
  def dp(rest,  dic):
    if rest in dic:
      return dic[rest]
    if rest == 0:
      return 0
    
    mask = 1  
    ret = 0
    for i in range(n):
      if rest & mask:
        pre_rest = rest & ~mask
        temp = dp(pre_rest, dic)
        temp = search(temp, i)
        ret = max(ret, temp)
      mask <<= 1
    dic[rest] = ret
    return ret
  
  print(dp(rest, dic))

main()