結果
問題 |
No.1515 Making Many Multiples
|
ユーザー |
|
提出日時 | 2024-12-30 21:38:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,592 bytes |
コンパイル時間 | 469 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 266,876 KB |
最終ジャッジ日時 | 2024-12-30 21:39:52 |
合計ジャッジ時間 | 57,010 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 TLE * 17 |
ソースコード
## https://yukicoder.me/problems/no/1515 MIN_VALUE = -10 ** 18 def main(): N, K, X, Y = map(int, input().split()) A = list(map(int, input().split())) dp = [[MIN_VALUE] * K for _ in range(K)] dp[X % K][Y % K] = 0 dp[Y % K][X % K] = 0 # max_valueの定義 max_dp_x = [MIN_VALUE] * K max_dp_y = [MIN_VALUE] * K max_dp_x[X % K] = 0 max_dp_x[Y % K] = 0 max_dp_y[X % K] = 0 max_dp_y[Y % K] = 0 answer = 0 for a in A: a_ = a % K updates = {} # 結局Aを捨てるもの for k_y in range(K): k_x_ = (- a_ - k_y) % K new_key = (k_x_, k_y) updates[new_key] = dp[k_x_][k_y] + 1 for k_y in range(K): k_x_ = (- a_ - k_y) % K new_key = (a_, k_y) if new_key not in updates: updates[new_key] = dp[a_][k_y] updates[new_key] = max(updates[new_key], dp[k_x_][k_y] + 1, max_dp_y[k_y]) for k_x in range(K): k_y_ = (- a_ - k_x) % K new_key = (k_x, a_) if new_key not in updates: updates[new_key] = dp[k_x][a_] updates[new_key] = max(updates[new_key], dp[k_x][k_y_] + 1, max_dp_x[k_x]) #更新 for key, value in updates.items(): x, y = key dp[x][y] = max(dp[x][y], value) max_dp_x[x] = max(max_dp_x[x], dp[x][y]) max_dp_y[y] = max(max_dp_y[y], dp[x][y]) answer = max(answer, dp[x][y]) print(answer) if __name__ == "__main__": main()