#603063 (PyPy3) No.1330 Multiply or Divide

• 問題: No.1330 Multiply or Divide
• ユーザー: ayaoni
• 提出日時: 2021-01-14 02:56:12
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 706 ms / 2,000 ms
• コード長: 1,297 bytes
• コンパイル時間: 192 ms
• コンパイル使用メモリ: 81,976 KB
• 実行使用メモリ: 121,148 KB
• 最終ジャッジ日時: 2024-11-23 02:02:34
• 合計ジャッジ時間: 8,244 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
other	AC * 46

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import sys
from operator import itemgetter
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())
N,M,P = MI()
A = LI()
max_A = max(A)
# 最後の1回の操作はmax_Aを掛ける
X = M//max_A+1  # 目標値
if X == 1:
    print(1)
    exit()
B = []
for a in A:
    r = 0
    while a % P == 0:
        r += 1
        a //= P
    B.append((r+1,-a))  # (操作回数,-(結局何倍になるか))
B = sorted(B,key=itemgetter(0,1))
C = []
r,a = B[0]
a *= -1
C.append((r,a))
for i in range(1,N):
    r,a = B[i]
    a *= -1
    if C[-1][0] < r and C[-1][1] < a:
        C.append((r,a))
for r,a in C:
    if a != 1:
        break
else:
    print(-1)
    exit()
dp = [1]*10000  # dp[i] = i回の操作でできる最大値
for i in range(1,10000):
    for r,a in C:
        if i >= r:
            dp[i] = max(dp[i],dp[i-r]*a)
    if dp[i] >= X:
        print(i+1)  # 最後の1回の操作を追加
        break
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX