結果

問題 No.1515 Making Many Multiples
ユーザー tktk_snsn
提出日時 2021-05-24 21:15:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 837 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 269,312 KB
最終ジャッジ日時 2024-10-13 05:33:50
合計ジャッジ時間 3,868 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
N, K, X, Y = map(int, input().split())
X %= K
Y %= K
if X > Y:
    X, Y = Y, X
A = list(map(int, input().split()))

dp = [[-1] * K for _ in range(K)]
dp[X][Y] = 0
cand = [X * K + Y, ]

for a in A:
    a %= K
    memo = defaultdict(int)
    for xy in cand:
        x, y = divmod(xy, K)
        score = dp[x][y] + int((x + y + a) % K == 0)
        memo[x*K+y] = max(memo[x*K+y], score)
        xi = min(x, a)
        yi = max(x, a)
        memo[xi*K+yi] = max(memo[xi*K+yi], score)
        xi = min(y, a)
        yi = max(y, a)
        memo[xi*K+yi] = max(memo[xi*K+yi], score)

    cand = []
    for xy, score in memo.items():
        x, y = divmod(xy, K)
        dp[x][y] = score
        cand.append(xy)

ans = 0
for i in range(K):
    for j in range(i, K):
        ans = max(ans, dp[i][j])
print(ans)
0