結果
問題 | No.3014 岩井満足性問題 |
ユーザー |
|
提出日時 | 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 |
ソースコード
import syssys.setrecursionlimit(10 ** 6)# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')from collections import defaultdict as ddS = inputR = rangeP = printdef 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 ** 18mod = 998244353dxy4 = [(-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 bdef gin(N, M):g = [[] for _ in range(N)]for _ in range(M):u, v = map(int, input().split())u -= 1v -= 1g[u].append(v)g[v].append(u)return gn,d,k=M();a=L();c=L()dp=[[-inf]*(k+1)for _ in R(d+1)]dp[0][0]=0for 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:continueif 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=ndpans=dp[d][k];P("No"if ans==-inf else ans)