Skip to content

Instantly share code, notes, and snippets.

@uchidama
Created July 15, 2021 16:09
Show Gist options
  • Save uchidama/e636febd3fd2d9c45f2e87cbaacea465 to your computer and use it in GitHub Desktop.
Save uchidama/e636febd3fd2d9c45f2e87cbaacea465 to your computer and use it in GitHub Desktop.
AtCoder Beginner Contest 172 [ C - Tsundoku ] https://atcoder.jp/contests/abc172/tasks/abc172_c
'''
[問題]
https://atcoder.jp/contests/abc172/tasks/abc172_c
[参考]
https://blog.hamayanhamayan.com/entry/2020/06/27/230511
 変形?しゃくとり法で数列A、Bを走査する
[結果]
PyPy3(7.3.0) AC 146ms
Python(3.8.2) AC 319ms
'''
import sys
sys.setrecursionlimit(10 ** 6) # 再帰上限の引き上げ
input = sys.stdin.readline
INF = 2 ** 63 - 1
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
SUM_A = [0] * (N + 1)
SUM_B = [0] * (M + 1)
for i in range(1, N+1):
SUM_A[i] = SUM_A[i-1] + A[i-1]
for i in range(1, M+1):
SUM_B[i] = SUM_B[i-1] + B[i-1]
ans = 0
b = M
# 数列Aは0から走査
for a in range(N+1):
# 数列Bは最大から減らす方向に走査。Aが増えればBは必ず減少方向に動くはず
while 0 <= b and (K < SUM_B[b] + SUM_A[a]):
b -= 1
if 0 <= b:
ans = max(ans, b + a)
print(ans)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment