結果
問題 |
No.1515 Making Many Multiples
|
ユーザー |
|
提出日時 | 2024-12-30 21:46:13 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,590 bytes |
コンパイル時間 | 372 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 252,348 KB |
最終ジャッジ日時 | 2024-12-30 21:47:05 |
合計ジャッジ時間 | 52,071 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 TLE * 16 |
ソースコード
## 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)] update_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 # 結局Aを捨てるもの array = [] for k_y in range(K): k_x_ = (- a_ - k_y) % K update_dp[k_x_][k_y] = dp[k_x_][k_y] + 1 array.append((k_x_, k_y)) for k_y in range(K): k_x_ = (- a_ - k_y) % K update_dp[a_][k_y] = max(update_dp[a_][k_y], dp[a_][k_y], dp[k_x_][k_y] + 1, max_dp_y[k_y]) array.append((a_, k_y)) for k_x in range(K): k_y_ = (- a_ - k_x) % K update_dp[k_x][a_] = max(update_dp[k_x][a_], dp[k_x][a_], dp[k_x][k_y_] + 1, max_dp_x[k_x]) array.append((k_x, a_)) #更新 for x, y in array: if dp[x][y] < update_dp[x][y]: dp[x][y] = max(dp[x][y], update_dp[x][y]) 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]) update_dp[x][y] = MIN_VALUE print(answer) if __name__ == "__main__": main()