結果

問題 No.3014 岩井満足性問題
ユーザー hiro1729
提出日時 2025-01-25 12:48:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 871 ms / 3,000 ms
コード長 1,309 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 254,328 KB
最終ジャッジ日時 2025-01-25 22:21:50
合計ジャッジ時間 5,651 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge8
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10 ** 6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict as dd
S = input
R = range
P = print
def I(): return int(S())
def M(): return map(int, S().split())
def L(): return list(M())
def O(): return list(map(int, open(0).read().split()))
def yn(b): print("Yes" if b else "No")
biga = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
smaa = "abcdefghijklmnopqrstuvwxyz"
ctoi = lambda c: ord(c) - ord('a')
ctoi2 = lambda c: ord(c) - ord('A')
itoc = lambda i: chr(ord('a') + i)
itoc2 = lambda i: chr(ord('A') + i)
inf = 10 ** 18
mod = 998244353
dxy4 = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dxy8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def acc(a):
	b = [0]
	for i in a:
		b.append(b[-1] + i)
	return b
def gin(N, M):
	g = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	return g

n,d,k=M();a=L();c=L()
dp=[[-inf]*(k+1)for _ in R(d+1)]
dp[0][0]=0
for i in R(n):
	ndp=[[-inf]*(k+1)for _ in R(d+1)]
	for j in R(d+1):
		for l in R(k+1):
			if dp[j][l]==-inf:
				continue
			if j<d:
				ndp[j+1][min(k,l+c[i])]=max(ndp[j+1][min(k,l+c[i])],dp[j][l]+a[i])
			ndp[j][l]=max(ndp[j][l],dp[j][l])
	dp=ndp
ans=dp[d][k];P("No"if ans==-inf else ans)
0