Edit

【pythonでABC172を解説】C - Tsundoku

問題概要

問題ページ

C - Tsundoku
C - Tsundoku

問題ページへ移動する

問題文

二台の机 A, B があります。机 A には \(N\) 冊の本が、机 B には \(M\) 冊の本が、それぞれ縦に積まれています。

机 A に現在上から \(i\) 番目に積まれている本 \((1 \leq i \leq N)\) は読むのに \(A_i\) 分を要し、机 B に現在上から \(i\) 番目に積まれている本 \((1 \leq i \leq M)\) は読むのに \(B_i\) 分を要します。

次の行為を考えます。

  • 本が残っている机を選び、その机の最も上に積まれた本を読んで机から取り除く。

合計所要時間が \(K\) 分を超えないようにこの行為を繰り返すとき、最大で何冊の本を読むことができるでしょうか。本を読むこと以外に要する時間は無視します。

制約

  • \(1 \leq N, M \leq 200000\)
  • \(1 \leq K \leq 10^9\)
  • \(1 \leq A_i, B_i \leq 10^9\)
  • 入力中の値はすべて整数である。

問題の考察

ACコード

import sys
import itertools
import bisect


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m, k = list(map(int, input().rstrip('\n').split()))
    a = [0] + list(itertools.accumulate(list(map(int, input().rstrip('\n').split()))))
    b = list(itertools.accumulate(list(map(int, input().rstrip('\n').split()))))
    mx = 0
    for i in range(n + 1):
        if a[i] <= k:
            p = bisect.bisect_right(b, k - a[i])
            mx = max(mx, i + p)
        else:
            break
    print(mx)


if __name__ == '__main__':
    solve()

-Edit
-