結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
62,104 KB |
| testcase_01 | AC | 61 ms
69,916 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
ソースコード
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)