結果

問題 No.393 2本の竹
コンテスト
ユーザー hiyokko2
提出日時 2016-07-30 20:02:22
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 831 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 54,120 KB
最終ジャッジ日時 2024-11-06 21:22:06
合計ジャッジ時間 3,173 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 7 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

def rec(i, r1):
	#if dp[i][r1] != -1:
	#	return dp[i][r1]
	if i in dphash and r1 in dphash[i]:
		return dphash[i][r1]
	r2 = n1 + n2 - Asum[i - 1] - r1
	if i == m:
		res = 0
	elif max(r1, r2) < A[i]:
		res = 0
	elif r1 < A[i] and A[i] < r2:
		res = rec(i + 1, r1) + 1
	elif r2 < A[i] and A[i] < r1:
		res = rec(i + 1, r1 - A[i]) + 1
	else:
		res = max(rec(i + 1, r1), rec(i + 1, r1 - A[i])) + 1
	#dp[i][r1] = res
	if i in dphash:
		dphash[i][r1] = res
	else:
		dphash[i] = {}
		dphash[i][r1] = res
	return res

d = int(input())
for _ in range(d):
	n1, n2 = map(int, input().split())
	m = int(input())
	A = sorted(map(int, input().split()))

	Asum = []
	Asum.append(A[0])
	for i in range(1, m):
		Asum.append(Asum[i - 1] + A[i])
	#print(Asum)
	#dp = [[-1 for r1 in range(100001)] for i in range(61)]
	dphash = {}
	print(rec(0, n1))
0