結果

問題 No.3696 Betting Machine
コンテスト
ユーザー shobonvip
提出日時 2026-09-09 21:58:29
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 285 ms / 1,500 ms
+ 809µs
コード長 688 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 72 ms
コンパイル使用メモリ 81,732 KB
実行使用メモリ 87,296 KB
最終ジャッジ日時 2026-09-09 21:58:35
合計ジャッジ時間 4,712 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from fractions import Fraction

s,t,n=map(int,input().split())
p=[0]*3;a=[0]*3;b=[0]*3
for i in range(3):
	p[i],a[i],b[i]=map(int,input().split())

mx = t
dp = [[0 for j in range(t+1)] for i in range(n+1)]

for j in range(n+1):
	dp[j][t] = 100**(n-j)

for i in range(n-1,-1,-1):
	for j in range(t-1,-1,-1):
		for x in range(1,j+1):
			alt = 0
			for g in range(3):
				f = j - x + a[g]*x//b[g]
				alt += dp[i+1][min(f,t)] * p[g];
			dp[i][j] = max(dp[i][j], alt)

ans = []
for x in range(1,s+1):
	alt = 0
	for g in range(3):
		f = s - x + a[g]*x//b[g]
		alt += dp[1][min(f,t)] * p[g];
	if dp[0][s] == alt:
		ans += [x]

ft = dp[0][s]
print(ft // 100 ** (n-1))
print(len(ans))
print(*ans)
0